Olimpiade Sains Nasional (OSN) 2006 - Komputer
1.
Jawab →Runtuh
Batas Waktu : 1 detik
Batas Memori :32 MB
Runtuh adalah sebuah permainan yang bertujuan untuk membuat penuh satu baris dari sebuah papan menggunakan beberapa bangun yang disediakan. Jika sebuah baris penuh terisi maka baris tersebut akan dihilangkan dan sisa bangun di atasnya akan "diruntuhkan" satu demi satu turun melewati ruang yang telah kosong sampai menumpuk di atas bangun yang ada di bawahnya. Penumpukan yang terjadi dapat menghasilkan situasi seperti pada saat awal di atas yaitu terdapat baris-baris yang penuh terisi, yang selanjutnya akan dihilangkan lagi (setelah semua runtuh). Demikian berlangsung bisa berulang-ulang sampai tidak ada lagi baris yang penuh terisi.
Anda akan diberikan sebuah kondisi papan yang terdiri atas R (1 ? R ? 20) baris dan C (1 ? C ? 8) kolom dari suatu permainan ini untuk ditentukan kondisi akhirnya. Misalnya untuk papan seperti di bawah ini:
Kondisi papan setelah baris yang terisi penuh dihilangkan, akan menyisakan ruang kosong seperti di bawah ini:
Bangun-bangun yang terletak di atas baris terbawah yang dihilangkan akan diruntuhkan ke bawah sehingga kondisi papan setelah terjadi penurunan adalah seperti di bawah ini:
Dalam contoh di atas kebetulan keruntuhan hanya sekali saja. Namun, dalam beberapa kasus uji bisa aja terjadi keruntuhan berulang-ulang.
Format Masukan
Baris pertama berisi dua buah bilangan bulat R dan C. R baris berikutnya masing-masing berisi C buah karakter '0' atau '1'. Karakter '1' menandakan adanya bangun pada posisi tersebut.
Format Keluaran
R buah baris, masing-masing berisi C buah karakter yaitu kondisi akhir dari papan permainan tersebut.
Contoh Masukan
11 6 000000 000000 011100 110011 111111 111000 111111 111111 111001 001100 111011
Contoh Keluaran
000000 000000 000000 000000 000000 010000 111000 111001 111101 001110 111011
2.
Ulang Tahun
Batas waktu : 1 detik
Batas memori : 32MB
Beberapa hari lagi, Pak Dengklek akan merayakan ulang tahunnya yang ke-61. Beliau bermaksud akan mengundang teman-temannya untuk menghadiri pesta ulang tahunnya tersebut. Sayangnya, beliau baru saja kehilangan satu-satunya buku telepon yang dipunyainya. Karena itu, ia harus mengunjungi wartel terdekat dan membuka buku kuning untuk mengetahui nomor telepon teman-temannya. Tidak lupa ia mengajak Anda untuk membantunya mencarikan nomor telepon teman-temannya tersebut.
Diberikan buku kuning yang berisi N (1 ? N ? 10.000) pasangan nama dan nomor telepon seluruh penduduk desa tempat Pak Dengklek tinggal, serta Q (1 ? Q ? 10.000) nama teman Pak Dengklek yang tinggal di desa tersebut, tolonglah Pak Dengklek untuk mencari nomor telepon teman-teman Pak Dengklek tersebut.
Format Masukan
Baris pertama berisi dua buah bilangan bulat N dan Q. N baris selanjutnya berisi nama dan nomor telepon setiap orang di desa tersebut, dipisahkan dengan spasi. Q baris selanjutnya berisi nama-nama teman Pak Dengklek.
Nama setiap orang hanya akan tersusun dari huruf kapital, dengan panjang maksimal 15 huruf. Daftar nama pada buku kuning akan terurut sesuai abjad, tetapi daftar teman Pak Dengklek yang akan dicari nomor telponnya belum tentu terurut dan satu teman Pak Dengklek bisa saja ditanyakan lebih dari sekali. Setiap nomor telepon terdiri atas tepat 7 angka, satu nomor telepon dapat dimiliki oleh lebih dari satu orang. Semua teman pak Dengklek yang akan dicari nomor telponnya pasti tercantum dalam buku kuning.
Format Keluaran
Q buah baris, masing-masing berisi nomor telepon dari teman yang ditanyakan oleh Pak Dengklek.
Contoh Masukan
10 5 ACONG 8468431 BALAJI 1573547 GREGOR 1765743 JAPRA 3746843 JOKO 1357891 MALARANGENG 1375638 MANMOHAN 1357562 SITORUS 1378651 TERRY 8756345 YUDHOYONO 1781945 GREGOR YUDHOYONO ACONG MANMOHAN JAPRA
Contoh Keluaran
1765743 1781945 8468431 1357562 3746843
3.
Tebak Lagu
Batas waktu :1 detik
Batas memori : 32MB
Pak Dengklek dan bebek-bebeknya punya permainan baru, yaitu tebak lagu. Sesuai namanya, dalam permainan ini salah satu bebek akan menyanyikan fragmen/potongan sebuah lagu untuk kemudian ditebak oleh Pak Dengklek. Karena tahu bahwa Pak Dengklek bukanlah seorang penghafal yang handal, para bebek menyiapkan sebuah buku yang berisikan daftar lagu yang akan mereka nyanyikan, lengkap dengan nadanya. Seperti halnya manusia, para bebek tidak menyanyi dengan ketinggian nada yang sama satu sama lain. Oleh sebab itu, mereka sepakat untuk menuliskan nada-nada lagu di buku lagu mereka dalam nada dasar C tengah (C4 pada piano manusia, yang mereka beri simbol c.), yaitu nada dengan frekuensi 261.6 Hz. Untuk nada-nada yang lain, perhatikan daftar lengkap nada, simbol, dan frekuensi yang digunakan oleh para bebek (terurut menaik berdasar ketinggian nada), yang diberikan pada tabel di bawah ini:
Sebagai contoh, misalkan ada dua bebek (bebek Kwek dan bebek Kwak) yang akan menyanyikan sebuah lagu yang sama. Bebek Kwek menyanyikan lagu tersebut dalam nada dasar D4 (d.) dan bebek Kwak menyanyikannya dalam nada dasar E4 (e.). Rangkaian nada yang mereka nyanyikan adalah:
Bebek Kwek: d.e.f#e.d.
Bebek Kwak: e.f#g#f#e.
Sedangkan dalam buku lagu mereka, lagu tersebut akan dituliskan sebagai c.d.e.d.c.. Karena perbedaan nada dasar itulah, meski dapat mengenali nada dengan sangat akurat, Pak Dengklek merasa kesulitan dalam menebak lagu apa yang para bebeknya nyanyikan. Karena itulah, Olimpiade Sains Nasional V Bidang Informatika Pak Dengklek meminta bantuan Anda untuk membuatkan sebuah program yang dapat mengetahui lagu mana yang dinyanyikan para bebek. Informasi yang akan Pak Dengklek berikan pada Anda adalah:
1. Potongan lagu yang didengar oleh Pak Dengklek (dengan nada dasar sesuai yang dinyanyikan bebek yang bersangkutan).
2. Banyaknya lagu yang ada pada buku lagu bebek.
3. Rangkaian nada dari lagu-lagu dalam buku lagu tersebut.
Format Masukan
Baris pertama berisikan serangkaian karakter yang merepresentasikan rangkaian nada yang ingin dicari (sesuai simbol pada tabel pada deskripsi soal). Baris kedua berupa sebuah bilangan bulat n (1 <= n <= 100) yang menunjukkan banyaknya data lagu yang ada. n baris berikutnya berisikan data lagu yang tersedia, masing-masing dalam satu baris. Tiap baris masukan rangkaian nada terdiri atas tidak lebih dari 250 karakter.
Format Keluaran
Nomor lagu yang di dalamnya terdapat rangkaian nada yang bersesuaian dengan nada yang dicari, atau # jika rangkaian nada yang dicari tidak ditemukan. Penomoran lagu dimulai dari 1 (i.e. baris setelah integer n pada masukan merupakan data lagu ke-1). Jika ada lebih dari satu lagu yang bersesuaian dengan potongan lagu yang diberikan, tuliskan lagu dengan nomor terkecil saja.
Contoh Masukan 1
g.g.g.f.e.d.c.
6
d.c.e.d.c.f.e.d.g.g.g.f.e.d.e.
c.d.e.c#d.e.f#a.d.c.
c.d#e.
c.d.e.f.g.g.g.d.e.f.c.d.e.
c.c#d.d#e.f.f#g.g#a.a#b.C.
G.F.D#G#G.F.A#A#A#G#G.F.D#
Contoh Keluaran 1
6
Contoh Masukan 2
c.d.e.
1
C.D.C.
Contoh Keluaran 2
#
4.
Lihat 4 jawaban →Faktorial
Batas waktu : 1 detik
Batas memori : 32MB
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