Bantu temanmu belajar dengan menambahkan soal di Kujawab. Klik disini..

Olimpiade Sains Nasional (OSN) 2006 - Komputer

1

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

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