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

Olimpiade Sains Nasional (OSN) 2014 - Komputer , Nomor 1

1

4s, 256MB

Pokédex adalah sebuah komputer saku yang mutlak dimiliki oleh pelatih Pokémon untuk mengidentifikasi spesies Pokémon yang ditemui. Dengan mengarahkan Pokédex menghadap Pokémon, pengguna akan mendapatkan data lengkap mengenai Pokémon tersebut (seperti morfologi, informasi evolusi, dan kekuatan khusus) hampir secara instan. Namun apakah Anda tahu bagaimana proses yang terjadi di dalam Pokédex sehingga bisa menampilkan data yang sesuai dengan sangat cepat?

Pada Pokédex tertanam sebuah kamera mini khusus yang berfungsi merekam ciri-ciri dari Pokémon yang hendak diindentifikasi. Ciri-ciri ini akan direkam ketika pengguna mengarahkan Pokédex menghadap Pokémon. Dalam sekali proses identifikasi, kamera mini mampu merekam sebanyak N ciri-ciri. Ciri-ciri tersebut kemudian diterjemahkan ke dalam bahasa manusia (dalam kasus ini bahasa Inggris), lalu dilakukan pencocokan dengan database di Pokémon Center agar didapat nama beserta data lengkap Pokémon yang diidentifikasi. Hal yang menarik adalah proses penerjemahan sangat canggih sedemikian sehingga bahasa manusia yang didapat selalu merupakan substring dari data lengkap Pokémon tersebut di database.

Dalam pengembangan Pokédex generasi berikutnya, Anda direkrut oleh Professor Dengklek, seorang peneliti Pokémon ternama yang juga merupakan rekan sejawat Professor Oak, untuk mengimplementasikan algoritma pencocokan antara ciri-ciri yang direkam kamera mini khusus dengan database di Pokémon Center.

Pada pengembangan iterasi pertama, Anda hanya perlu mencocokkan data dari Pokémon generasi pertama. Professor Dengklek tidak memedulikan algoritma yang Anda gunakan, asalkan hasilnya dapat sangat akurat. Dapatkah Anda menyelesaikan tugas Anda dengan baik?

Format Masukan

Pada awalnya, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:

Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, dan berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:

Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Baris kedua berisi sebuah bilangan bulat N yang merupakan banyaknya ciri-ciri Pokémon yang direkam oleh kamera mini khusus pada Pokédex generasi terbaru.

Berikutnya terdapat N baris. Pada tiap baris berisi string S yang menyatakan hasil terjemahan ciri-ciri Pokemon ke dalam bahasa manusia. Seperti yang disinggung di soal, hasil terjemahan selalu merupakan substring dari data lengkap Pokémon tersebut di database.

Sebagai referensi, database Pokémon yang lengkap dapat diunduh di sini. Semua data yang terdapat dalam berkas tersebut diambil dari situs Bulbapedia.

Format Keluaran

Untuk ciri-ciri Pokémon yang diberikan, cetak keluaran dalam 1 baris berisi nama Pokémon yang dimaksud dari hasil analisis ciri-ciri Pokémon tersebut.

Contoh Masukan

0.....6
6
The flame that burns at the tip of its tail is an indication of its emotions
a bipedal, reptilian Pokemon with an orange body
A fire burns at the tip of this Pokemon’s slender tail
one of three starter Pokemon of Kanto available at the beginning of Pokemon Red, Green, Blue, FireRed, and LeafGreen
The flame at the tip of its tail makes a sound as it burns
Obviously prefers hot places


Contoh Keluaran

Charmander

 

Subsoal

Pada semua subsoal berlaku:

  • 4 ? N ? 10
  • 1 ? |S| ? 150
  • Dijamin nama Pokémon tersebut tidak akan muncul pada ciri-ciri Pokémon yang diberikan.

Subsoal 1 (3 poin)

  • Hanya terdapat sebuah kasus uji untuk subsoal ini, yang dapat diunduh di sini.

Subsoal 2 (4 poin)

  • Hanya terdapat sebuah kasus uji untuk subsoal ini, yang dapat diunduh di sini.

Subsoal 3 (5 poin)

  • Hanya terdapat sebuah kasus uji untuk subsoal ini, yang dapat diunduh di sini.

Subsoal 4 (4 poin)

  • Hanya terdapat sebuah kasus uji untuk subsoal ini, yang dapat diunduh di sini.

Subsoal 5 (3 poin)

  • Hanya terdapat sebuah kasus uji untuk subsoal ini, yang dapat diunduh di sini.

Subsoal 6 (hingga 81 poin)

  • Untuk subsoal ini, terdapat 45 kasus uji. Berbeda dengan model subsoal umum, pada subsoal ini semua kasus uji akan dinilai secara independen (Anda akan tetap mendapat nilai untuk kasus uji yang benar walaupun ada beberapa kasus uji yang salah).