Archive for 2014
Nah ini yang dari kemaren banyak temen2 yang nunggu,
udah lebih dari 1 bulan dinas pendidikan jateng blm ngasih info yang jelas tentang hasil osk tersebut.
Dan pada hari ini, udah dapat di lihat hasilnya.
Langsung aja di web resminya.
atau
Mirror
Selamat bagi yang lolos,
Yang belum lolos harus semangat buat UN dan semesteran.
udah lebih dari 1 bulan dinas pendidikan jateng blm ngasih info yang jelas tentang hasil osk tersebut.
Dan pada hari ini, udah dapat di lihat hasilnya.
Langsung aja di web resminya.
atau
Mirror
Selamat bagi yang lolos,
Yang belum lolos harus semangat buat UN dan semesteran.
Untuk sekedar menambah wawasan para pembaca,
pada post kali ini.
saya ingin mengingatkan kembali apa sih relasinya FPB dengan KPK
pacaran ? LDR ? ato HTS ? ato yang lain :D
engga bukan gitu maksudnya
jadi gini ambil 2 bilangan bulat ( misal a dan b).
KPK(a,b) x FPB(a,b) = a x b
atau
LCM(a,b) x GCD(a,b) = a x b
mari kita buktikan :)
1. a dan b bernilai 8,10
jadi kpk(8,10) x fpb(8,10) = 8 x10
40 x 2 = 8 x 10 => 80
2, a dan b bernilai 7 13
jadi kpk(7,13) x fpb(7,13) = 7 x 13
84 x 1 = 7 x 13 => 84
Terimakasih atas kunjungannya, jangan lupa tinggalkan komentar :)
pada post kali ini.
saya ingin mengingatkan kembali apa sih relasinya FPB dengan KPK
pacaran ? LDR ? ato HTS ? ato yang lain :D
engga bukan gitu maksudnya
jadi gini ambil 2 bilangan bulat ( misal a dan b).
KPK(a,b) x FPB(a,b) = a x b
atau
LCM(a,b) x GCD(a,b) = a x b
mari kita buktikan :)
1. a dan b bernilai 8,10
jadi kpk(8,10) x fpb(8,10) = 8 x10
40 x 2 = 8 x 10 => 80
2, a dan b bernilai 7 13
jadi kpk(7,13) x fpb(7,13) = 7 x 13
84 x 1 = 7 x 13 => 84
Terimakasih atas kunjungannya, jangan lupa tinggalkan komentar :)
Pecahan Uang
| Time limit | 1s / testcase |
| Memory limit | 16MB |
DESKRIPSI
Diberikan sebuah nilai uang dalam Dolar sebesar K, Buatlah sebuah program yang akan menghasilkan pecahan dolar bernilai total K dengan memakai uang pecahan terbesar. Jika uang pecahan terbesar tidak dapat dipakai (karena jumlah uang akan melebihi pecahan terbesar), maka diambil pecahan yang lebih kecil, dan seterusnya.
Pecahan yang tersedia adalah 1 dolar, 2 dolar, 5 dolar, 10 dolar, 20 dolar, 50 dolar, 100 dolar, 200 dolar, 500 dolar, dan 1000 dolar.
FORMAT MASUKAN
Baris pertama berisi sebuah bilangan bulat K (1 ≤ K ≤ 10000), yang merupakan jumlah uang yang harus dipecah.
FORMAT KELUARAN
Keluaran terdiri atas satu atau lebih. Masing-masing baris berisi dua buah bilangan bulat dipisahkan oleh sebuah spasi. Bilangan pertama adalah pecahan uang, dan bilangan kedua adalah banyak lembar untuk pecahan uang tersebut. Urutkanlah baris-baris berdasarkan pecahan uang, dari besar ke kecil. Pecahan uang yang tidak digunakan tidak perlu ditulis.CONTOH MASUKAN 1
98
CONTOH KELUARAN 1
50 1
20 2
5 1
2 1
1 1
CONTOH MASUKAN 2
10000
CONTOH KELUARAN 2
1000 10
Penyelesaian
Dalam dunia pemrograman komputer, istilah "swap" tentu sudah tidaklah asing lagi. Swap merupakan suatu cara untuk menukarkan nilai antar variabel.
Semisal kita mempunyai 2 variabel yang akan ditukar, sebut saja "x" dan "y".
Berdasarkan beberapa sumber yang saya dapati, ada 2 cara swapping :
Semisal kita mempunyai 2 variabel yang akan ditukar, sebut saja "x" dan "y".
Berdasarkan beberapa sumber yang saya dapati, ada 2 cara swapping :
- Menggunakan Temporary
- temporary adalah variabel sementara untuk menampung nilai.
- t := x;
x := y;
y :=t; - Menggunakan operasi bilangan
- x := x + y;
- y := x -y ;
- x := x -y;
- Menggunakan logic gate XOR
- Dengan menggunakan gerbang logika XOR didapati 2 cara.:
- x := x xor y;
y := x xor y;
x := x xor y; - t := x xor y;
x := t xor x;
y := t xor x;
Pemberat
| Batas Waktu | 0,1 detik |
| Batas Memori | 16 MB |
Setelah membeli beberapa ekor kucing, kini Pak Dengklek memiliki dua jenis binatang di kebun belakang rumahnya. Kucing dan bebek tentunya. Di belakang rumahnya tersebut, Pak Dengklek juga memiliki sebuah jungkat-jungkit untuk kucing dan bebeknya bermain.
Agar tidak dinilai pilih kasih, untuk setiap kali permainan jungkat-jungkit, Pak Dengklek selalu mengatur sedemikian rupa sehingga di satu sisi pastilah seekor bebek dan di sisi lainnya pastilah seekor kucing. Sayangnya semua kucing Pak Dengklek gemuk-gemuk sehingga berat kucing terkurus Pak Dengklek pun tetap lebih besar dari berat bebek tergemuk. Oleh karena itu jungkat-jungkit Pak Dengklek sering kali lebih berat ke sisi di mana kucing berada dan permainan pun tidak berjalan dengan mengasyikan.
Untuk mengatasi masalah ini, dasar Pak Dengklek yang banyak akalnya, ia menggunakan beberapa pemberat di sisi bebek berada, sedemikian sehingga berat satu sisi dan lainnya kini sama. Sayangnya Pak Dengklek tidak memiliki pemberat dalam setiap ukuran, Pak Dengklek hanya memiliki pemberat dengan ukuran 2^K dengan 0 ≤ K ≤ 60. Terlebih lagi, Pak Dengklek hanya memiliki satu buah pemberat untuk setiap ukuran tersebut.
Saat ini berat bebek yang bermain adalah B, sedangkan berat kucing yang bermain adalah K (1 ≤ B < K ≤ 2^61). Bantulah Pak Dengklek untuk menentukan pemberat mana saja yang harus ia gunakan.
Format Masukan
Baris pertama berisi sebuah bilangan bulat B. Baris kedua berisi sebuah bilangan bulat K.
Format Keluaran
Beberapa baris dengan satu bilangan bulat setiap barisnya yang merupakan berat dari masing-masing pemberat yang digunakan Pak Dengklek, terurut dari besar ke kecil.
Contoh Masukan 1
1 6
Contoh Keluaran 1
4 1
Contoh Masukan 2
10 101
Contoh Keluaran 2
64 16 8 2 1
Penyelesaian
Faktorial
| Batas Waktu | 1 detik |
| Batas Memori | 16 MB |
N!, yaitu N faktorial, didefinisikan sebagai N x (N-1) x (N-2) x ... x 1.
Pak Dengklek memberikan Anda sebuah bilangan bulat N (1 ≤ N ≤ 10.000). Hitunglah jumlah 0 berurutan yang mengakhiri N!. Misalnya, 10! = 3.628.800, maka jumlah 0 berurutan adalah 2. 8! = 40.320, maka jumlah 0 berurutan adalah 1 (nol di tengah tidak dihitung).
Format Masukan
Baris pertama berisi sebuah bilangan bulat N.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yaitu jawaban yang dimaksud.
Contoh Masukan 1
10
Contoh Keluaran 1
2
Contoh Masukan 2
8
Contoh Keluaran 2
1
Penyelesaian
Kelipatan 4 atau 7
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Bilangan 4 dan 7 selalu menarik perhatian Pak Dengklek. Kali ini ia meminta Anda untuk menghitung jumlah semua bilangan asli yang tidak lebih besar dari N (1 ≤ N ≤ 1.001.000) yang merupakan kelipatan 4 atau 7.
Misalnya, bilangan asli yang tidak lebih besar dari 10 yang merupakan kelipatan 4 atau 7 adalah 4, 7, dan 8. Jumlah dari keempat bilangan ini adalah 19.
Format Masukan
Baris pertama berisi sebuah bilangan bulat T (1 ≤ T ≤ 100.000) yaitu jumlah pertanyaan Pak Dengklek. T baris berikutnya masing-masing berisi sebuah bilangan bulat N.
Format Keluaran
T buah baris, masing-masing berisi sebuah bilangan bulat yaitu jumlah yang dimaksud.
Contoh Masukan
1 10
Contoh Keluaran
19
Penyelesaian
Magic Square
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Magic Square adalah persegi yang terdiri atas N x N petak, masing-masing petak berisi sebuah bilangan bulat antara 1 hingga N2 tanpa ada 2 petak yang berisi angka yang sama, di mana jumlah bilangan yang ada pada setiap baris = jumlah bilangan yang ada pada setiap kolom = jumlah bilangan yang terletak pada setiap diagonal utama. Yang dimaksud dengan diagonal utama di sini adalah diagonal yang membentang dari pojok kiri atas hingga ke pojok kanan bawah, dan diagonal yang membentang dari pojok kanan atas hingga pojok kiri bawah persegi. Tentu saja sebuah Magic Square berukuran setidaknya 3 x 3 memiliki tepat dua buah diagonal utama.
Pak Dengklek memberikan Anda beberapa pertanyaan yang masing-masing diwakilkan dengan sebuah bilangan bulat N (3 ≤ N ≤ 1.000.000). Untuk setiap bilangan bulat N yang ditanyakan, tentukan jumlah bilangan pada baris pertama magic square berukuran N x N.
Format Masukan
Baris pertama berisi bilangan bulat T (1 ≤ T ≤ 100.000) yaitu banyaknya pertanyaan Pak Dengklek. Sebanyak T baris berikutnya masing-masing berisi sebuah bilangan bulat N, yang mewakili pertanyaan Pak Dengklek.
Format Keluaran
Sebanyak T baris, masing-masing berisi sebuah bilangan bulat yang merupakan nilai K untuk setiap N yang ditanyakan, sesuai dengan urutan pada masukan.
Contoh Masukan
2 3 4
Contoh Keluaran
15 34
Penyelesaian
Penjumlahan Pecahan
| Batas Waktu | 1 detik |
| Batas Memori | 16 MB |
Pak Dengklek memberikan Anda dua buah pecahan dalam bentuk A/B dan C/D. Hitunglah A/B + C/D, lalu cetak hasilnya dalam bentuk yang paling sederhana. Bentuk paling sederhana dari suatu pecahan adalah ketika FPB dari pembilang dan penyebutnya adalah 1.
A, B, C, dan D adalah bilangan bulat positif yang muat dalam tipe data bilangan bulat 64-bit (int64 pada Free Pascal).
Format Masukan
Baris pertama berisi dua buah bilangan bulat A dan B. Baris kedua berisi dua buah bilangan bulat C dan D.
Format Keluaran
Sebuah baris berisi dua buah bilangan bulat, yaitu E dan F, di mana E/F = A/B + C/D dan E/F adalah bentuk yang paling sederhana. Dijamin E dan F muat dalam tipe data bilangan bulat 64-bit (int64 pada Free Pascal).
Contoh Masukan 1
2 3 4 5
Contoh Keluaran 1
22 15
Contoh Masukan 2
2 4 3 8
Contoh Keluaran 2
7 8
Penyelesaian
Prima Ke-K
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Pak Dengklek memberikan Anda T (1 ≤ T ≤ 20.000) buah pertanyaan. Setiap pertanyaan berbunyi, "apakah bilangan prima yang ke-K (1 ≤ K ≤ 77777)?"
Jawablah pertanyaan-pertanyaan tersebut.
Format Masukan
Baris pertama berisi sebuah bilangan bulat T. T baris berikutnya masing-masing berisi sebuah bilangan bulat K.
Format Keluaran
T buah baris, masing-masing berisi bilangan prima ke-K.
Contoh Masukan
4 1 3 5 2
Contoh Keluaran
2 5 11 3
Pembahasan
Sub-Persegi
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Suatu hari, putra Pak Dengklek pulang dari sekolah dengan sebuah pertanyaan sederhana. Ada berapa subpersegi, termasuk persegi itu sendiri, yang terdapat pada sebuah petak berukuran N x N (1 ≤ N ≤ 100)?
Format Masukan
Baris pertama berisi sebuah bilangan bulat N.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yaitu jumlah yang dimaksud.
Contoh Masukan 1
2
Contoh Keluaran 1
5
Contoh Masukan 2
8
Contoh Keluaran 2
204
Pembahasan
Faktor Persekutuan Terbesar
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
FPB (Faktor Persekutuan Terbesar) dari dua buah bilangan bulat A dan B adalah bilangan bulat non-negatif terbesar yang membagi A dan membagi B. Misalnya, FPB dari 12 dan 20 adalah 4.
FPB dari dua buah bilangan dapat dicari secara manual. Namun, ada cara yang lebih efisien yaitu menggunakan definisi rekursif sebagai berikut (disebut Algoritma Euclid):
- FPB dari 0 dan suatu bilangan sembarang adalah bilangan sembarang tersebut.
- FPB dari A dan B sama dengan FPB dari B dan (A mod B).
Gunakan definisi rekursif ini untuk membuat sebuah fungsi rekursif yang efisien untuk menghitung FPB dari dua buah bilangan, dan pakailah di dalam program Anda.
Pak Dengklek memberikan Anda T (1 ≤ T ≤ 10.000) pasang bilangan bulat A dan B (0 ≤ A, B ≤ 1.000.000.000). Tentukan FPB dari setiap pasang A dan B tersebut.
Format Masukan
Baris pertama sebuah bilangan bulat T. T baris berikutnya masing-masing berisi dua buah bilangan bulat A dan B.
Format Keluaran
T buah baris, masing-masing berisi sebuah bilangan bulat yaitu FPB dari A dan B.
Contoh Masukan
2 12 20 1 2
Contoh Keluaran
4 1
Pembahasan
Faktorisasi Prima
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Setiap bilangan bulat positif yang lebih besar daripada 1 adalah hasil perkalian dari sejumlah bilangan prima. Tepatnya, setiap bulangan bulat positif yang lebih besar daripada 1 adalah hasil perkalian dari pemangkatan sejumlah bilangan prima. Misalnya, 7 = 7, 20 = 22 x 5, dan 75 = 3 x 52.
Pak Dengklek memberikan Anda sebuah bilangan bulat N (1 ≤ N ≤ 1.000.000). Tentukan bilangan-bilangan prima a1, a2, ..., ak dan pangkat-pangkatnya, b1, b2, ..., bk, sehingga N = a1^b1 x a2^b2 x ... x ak^bk.
Format Masukan
Baris pertama berisi sebuah bilangan bulat N.
Format Keluaran
Sebuah baris berisi faktorisasi prima dari N dengan format a1^b1 x a2^b2 x ... x ak^bk. Bilangan prima a1, a2, ..., ak harus terurut dari kecil ke besar. Tanda pangkat diwakili dengan tanda '^' tanpa spasi, dan tanda kali diwakili oleh huruf 'x' kecil, diawali dan diikuti oleh sebuah spasi. Jika suatu pangkat bernilai 1, cukup ditulis faktornya saja.
Contoh Masukan 1
75
Contoh Keluaran 1
3 x 5^2
Pembahasan
Sebelumnya minta maaf kalo pembahasannya terlalu panjang, soal indentasi dan yg lain jg masih acak-acakan, sori banget yaa ~
Merge sort adalah algoritma yang berjalan dengan waktu O(N log N), yang jauh lebih efisien daripada O(N^2), dan akan berjalan jauh lebih cepat untuk N yang besar.
Algoritma merge sort sesungguhnya sangat sederhana: Bagi array menjadi dua sama besar, sort bagian pertama, sort bagian kedua, lalu gabungkan. Tentu sort ini menggunakan prosedur rekursif dengan parameter index paling kiri (a) dan index paling kanan (b).
Algoritma merge sort sesungguhnya sangat sederhana: Bagi array menjadi dua sama besar, sort bagian pertama, sort bagian kedua, lalu gabungkan. Tentu sort ini menggunakan prosedur rekursif dengan parameter index paling kiri (a) dan index paling kanan (b).
procedure
sort(terkiri,terkanan:longint);
begin
if terkiri < terkanan then
begin
sort(terkiri,(terkiri+terkanan) div 2);
sort(((terkiri+terkanan) div 2) + 1,
terkanan);
merge(terkiri,(terkiri+terkanan) div 2,
((terkiri+terkanan) div
2)+1,terkanan);
end;
end;
Quick Sort adalah algoritma sort yang tercepat dari antara sort-sort O(N log N) lainnya. Tetapi, Quick Sort juga algoritma yang running timenya tidak stabil. Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sangat cepat, tetapi pada kasus-kasus tertentu Quick Sort akan berjalan agak lambat, dan kalau sedang sial, untuk input tertentu (worst case) Quick Sort akan berjalan dengan waktu O(N2). Tapi pada umumnya (average case), Quick Sort berjalan dengan waktu O(N log N).
procedure
quicksort(terkiri,terkanan:longint);
var
kiri,kanan,temp,pivot:longint;
begin
if terkiri
begin
kiri:=terkiri;
kanan:=terkanan;
pivot:=data[(kiri+kanan) div 2];
while kiri<=kanan do
begin
while data[kiri]
while data[kanan]>pivot do dec(kanan);
if kiri<=kanan then
begin
temp:=data[kiri];
data[kiri]:=data[kanan];
data[kanan]:=temp;
inc(kiri);
dec(kanan);
end;
end;
quicksort(terkiri,kanan);
quicksort(kiri,terkanan);
end;
end;
Selection Sort merupakan sorting yang bisa dibilang cukup mudah dan bisa dilakukan di tempat (tanpa bantuan array lain).Dasarnya pada setiap langkah, carilah elemen terkecil yang tersisa lalu letakkan di depan.
procedure selectionsort;
var i,j,min,temp :integer;
begin
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
begin
if data[j] < data[min] then min:=j;
end;
if min <>i then
begin
temp:=data[min];
data[min]:=data[i];
data[i]:=temp;
end;
end;
end.
Keterangan :
i,j digunakan untuk looping.
data[] array bertipe integer (di deklarasikan pada program utama)
n adalah jumlah data (dideklarasikan pada program utama)
temp adalah var temporary digunakan untuk swap
Bubble sort merupakan sorting yang berprinsip pada sifat gelembung. Dasarnya, bilangan yg lebih kecil dari bilangan yang dibandingkan, akan di swap ke kiri (jika ascending).
Berikut Procedure Bubble Sort
Procedure BubbleSort;
var i,j,temp:integer // menyesuaikan masalah /soal
begin
for i := 1 to N do
for j := 1 to N - 1 do
if data[j] > data[j + 1] then
begin
temp := data[j];
data[j] := data[j + 1];
data[j + 1] := temp;
end;
end;
Keterangan :
data[] adalah array yang bernama data
n adalah jumlah data yang akan ditukar
temp adalah temporary, gunanya untuk tempat sementara agar bisa melakukan swap
Pustakawan
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Pak Dengklek mencoba bekerja paruh waktu menjadi pustakawan. Setiap hari, dia bertugas merapikan buku-buku di setiap rak sehingga urut sesuai nomor kodenya. Pak Dengklek merasa kerepotan karena harus menukar posisi buku-buku berkali-kali.
Kali ini, Pak Dengklek akan merapikan sebuah rak berisi N (1 ≤ N ≤ 1.000) buah buku. Buku ke-i memiliki kode Di (-32.768 ≤ Di < 32.768). Bantulah Pak Dengklek dengan menentukan jumlah penukaran buku minimum hingga buku dalam suatu rak terurut menaik berdasarkan nomor kodenya.
Format Masukan
Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya masing-masing berisi sebuah bilangan bulat Di. Dijamin kode-kode buku tersebut berbeda-beda.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yaitu jumlah penukaran minimum yang harus dilakukan untuk mengurutkan buku-buku tersebut.
Contoh Masukan
5124 35
Contoh Keluaran
2
Penyelesaian
