Olimpiade Sains Nasional (OSN) 2014 - Komputer
1.
Lihat 1 jawaban →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).
2.
1s, 32MB
Pak Dengklek mengunjungi kawasan wisata Candi Borobudur. Kawasan ini menarik karena banyak terdapat stupa yang indah. Sang penjaga berkata bahwa ada keajaiban di balik bilangan bulat yang terjadi pada kawasan tersebut. Untuk setiap bilangan bulat positif X, terdapat tepat 0 atau X buah stupa setinggi X meter.
Pak Dengklek, yang tidak sempat berkeliling ke seluruh kawasan, hanya sempat melihat N stupa. Tinggi dari stupa ke-i yang dilihatnya adalah Ai meter. Pak Dengklek pun penasaran mengenai banyaknya stupa di kawasan tersebut.
Tentukan banyaknya stupa minimum di kawasan wisata tersebut!
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. Baris berikutnya berisi N buah bilangan bulat A1, A2, ..., AN.
Format Keluaran
Sebuah baris berisi banyaknya stupa minimum. Apabila masukan tidak sesuai dengan perkataan sang penjaga (mungkin saja Pak Dengklek salah lihat!), keluarkan sebuah baris berisi -1.
Contoh Masukan 1
0..34567
5
2 1 4 2 3
Contoh Keluaran 1
10
Contoh Masukan 2
0..34567
4
2 9 2 2
Contoh Keluaran 2
-1
Subsoal
Subsoal 1 (7 poin)
- N = 10
- Ai = i
- Kasus uji dapat diunduh di sini.
Subsoal 2 (11 poin)
- N = 8
- 1 ? Ai ? 10
- Kasus uji dapat diunduh di sini.
Subsoal 3 (7 poin)
- N = 1
- 1 ? A1 ? 1.000
Subsoal 4 (11 poin)
- 1 ? N ? 1.000
- 1 ? A1 = A2 = ... = AN ? 1.000
Subsoal 5 (17 poin)
- 1 ? N ? 1.000
- 1 ? Ai ? 1.000
Subsoal 6 (20 poin)
- 1 ? N ? 100.000
- 1 ? Ai ? 100.000
Subsoal 7 (27 poin)
- 1 ? N ? 100.000
- 1 ? Ai ? 1.000.000.000
3.
1s, 32MB
Semoga Anda masih ingat soal Tebak Angka di mana Anda diharuskan menebak angka yang dipikirkan Pak Dengklek (dari rentang 1 hingga N) dengan menebak maksimal Q kali dan Pak Dengklek akan menjawab TERLALU KECIL, TERLALU BESAR, atau SELAMAT apabila berhasil menebak angka yang dipikirkan.
Sekarang, mari kita bertukar posisi!
Anda diminta untuk memikirkan sebuah angka dari rentang 1 hingga N. Anda dinyatakan menang apabila Pak Dengklek tidak dapat menebak angka yang Anda pikirkan hingga akhir tebakan (tebakan ke-Q).
Sama seperti strategi Anda pada soal Tebak Angka, Pak Dengklek memakai prinsip Divide & Conquer untuk menebak angka yang Anda pikirkan. Apabila angka yang Anda pikirkan berada pada rentang A hingga B, maka pak Dengklek akan menebak C = (A + B) / 2 sebagai angka yang Anda pikirkan. Apabila C bukan berupa bilangan bulat, maka secara acak Pak Dengklek akan memilih pembulatan ke atas atau pembulatan ke bawah. Tentu saja apabila Anda menjawab TERLALU BESAR maka angka yang Anda pikirkan berada pada rentang A hingga C - 1 dan apabila Anda menjawab TERLALU KECIL maka angka yang Anda pikirkan berada pada rentang C + 1 hingga B.
Perlu diperhatikan bahwa Pak Dengklek dapat mengecek apakah jawaban-jawaban Anda konsisten sehingga kecurangan-kecurangan yang bisa saja Anda lakukan secara otomatis akan langsung terdeteksi. Salah satu contoh kecurangan yaitu Anda menjawab TERLALU BESAR ketika Pak Dengklek menebak angka 1.
Format Interaksi
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.
Selanjutnya, program Anda akan menerima input dua buah bilangan N dan Q.
Kemudian, Anda akan menerima sebuah bilangan bulat C yaitu tebakan Pak Dengklek untuk angka yang Anda pikirkan. Anda diminta untuk menjawab TERLALU KECIL, TERLALU BESAR, atau SELAMAT berdasarkan angka yang Anda pikirkan.
Apabila Anda menjawab SELAMAT, artinya Pak Dengklek berhasil menebak angka yang Anda pikirkan dan Anda dinyatakan kalah. Apabila Anda menjawab selain SELAMAT, maka Pak Dengklek akan menebak kembali angka yang Anda pikirkan.
Anda dinyatakan menang apabila hingga tebakan ke-Q Pak Dengklek masih belum mendapatkan jawaban SELAMAT.
Contoh Interaksi
| Keluaran Program Peserta | Umpan Balik Grader |
|---|---|
| 0...4. | |
| 9 3 | |
| 5 | |
| TERLALU BESAR | |
| 2 | |
| TERLALU KECIL | |
| 4 | |
| TERLALU BESAR | |
| (interaksi selesai) |
Penjelasan Contoh Interaksi
Pada kasus tersebut, nilai N dan Q secara berturut-turut adalah 9 dan 3. Dari angka 1 hingga 9, Anda memilih angka 3.
Untuk tebakan pertama, nilai A dan B adalah 1 dan 9 sehingga C = (1 + 9) / 2 = 5.
Karena 5 terlalu besar dibandingkan dengan 3, maka Anda menjawab TERLALU BESAR. Sehingga untuk tebakan kedua, nilai A dan B adalah 1 dan 4. Karena nilai C = (1 + 4) / 2 = 2,5 bukan merupakan bilangan bulat, maka Pak Dengklek secara acak memilih untuk membulatkan ke bawah.
Karena 2 terlalu kecil dibandingkan dengan 3, maka Anda menjawab TERLALU KECIL. Sehingga untuk tebakan ketiga, nilai A dan B adalah 3 dan 4. Karena nilai C = (3 + 4) / 2 = 3,5 bukan merupakan bilangan bulat, maka Pak Dengklek secara acak memilih untuk membulatkan ke atas.
Karena 4 terlalu besar dibandingkan dengan 3, maka Anda menjawab TERLALU BESAR. Karena setelah Q = 3 tebakan Pak Dengklek tidak mendapatkan jawaban SELAMAT, maka Anda dinyatakan menang pada permainan ini.
Subsoal
Subsoal 1 (9 poin)
- N = 31
- Q = 4
Subsoal 2 (9 poin)
- N = 127
- Q = 6
Khusus untuk subsoal 1 dan subsoal 2:
- Hanya terdapat sebuah kasus uji (satu subsoal dinyatakan oleh satu kasus uji), yang dapat dimainkan di sini.
- Anda boleh memainkan permainan ini berulang kali tanpa mendapatkan penalti.
- Jika Anda sudah memenangkan permainan untuk subsoal tertentu, Anda dapat memilih pilihan pada permainan untuk mengeluarkan source code yang dapat langsung Anda kirimkan ke grader dan menjawab dengan benar pada subsoal yang telah Anda menangkan.
- Anda tidak diwajibkan memainkan permainan ini untuk mengerjakan kedua subsoal ini. Anda diperbolehkan untuk menulis kode Anda sendiri untuk mengerjakan kedua subsoal ini.
Subsoal 3 (20 poin)
- N = 4
- Q = 2
Subsoal 4 (27 poin)
- N = 9
- Q = 3
Subsoal 5 (35 poin)
- N = 16
- Q = 4
4.
1s, 32MB
Kwek dan Kwak, seperti layaknya bebek lain sedang seru-serunya bermain permainan “Rocket Duck”. Pada Rocket Duck, pemain menjalankan seekor bebek bernama “Rocky” yang ingin mencari arti hidup, yang diyakini berada diujung belahan dunia. Di luar dugaan, Rocky mencari arti hidup dengan cara yang tidak biasa dan ironis: melempar dirinya sejauh mungkin dengan alat pelontar (dan berharap mencapai ujung belahan dunia). Tentu ini cara yang ekstrim dan berbahaya. Tapi siapa peduli, Rocky hanyalah sebuah tokoh imaginer dalam sebuah game, yang terpenting bahwa permainan ini berhasil memikat banyak bebek muda.
Semua bebek ambisius mengejar high-score di Rocket Duck, begitu pula Kwek dan Kwak. Mereka membayangkan namanya terpampang pada tabel leaderboard, yang menjadi sebuah kepuasan tersendiri bagi mereka. Namun Kwek dan Kwak punya kehidupan lain, mereka tidak bisa terus menerus bermain Rocket Duck. Sehingga kemampuan mereka tidak sejago pemain lainnya. Untungnya Kwek dan Kwak kenal dengan Anda, sang programmer handal yang konon dapat menyelesaikan berbagai masalah hanya dengan hentakan jari-jemari di atas keyboard. Kini mereka memerlukan bantuan kalian untuk mengejar high-score pada permainan Rocket Duck.
Rocket Duck adalah permainan 2D, di mana pemain berusaha mencapai jarak terjauh dengan menggunakan alat pelontar bebek. Alat ini dapat melontarkan bebek pada derajat dan kecepatan awal tertentu. Bebek kemudian bergerak secara parabola, hingga akhirnya jatuh ke tanah. Nilai yang didapat dari pemain adalah jarak yang dicapai. Makin jauh jarak yang dicapai, makin tinggi nilai yang didapat. Mekanisme lontaran roket mengikuti mekanisme dasar gerak parabolik. Berikut ini adalah ilustrasi mekanisme dari gerak parabolik:
Untuk Pemain, akan disediakan beberapa pilihan roda gigi untuk merakit pelontar bebek. Setiap roda gigi memiliki dua properti, yaitu nilai kecepatan K dan nilai sudut S. Sebuah pelontar bebek nantinya akan terdiri dari beberapa roda gigi yang terpasang pada mesin. Sudut akhir dari mesin pelontar ini adalah total nilai sudut dari semua roda gigi yang dipasang. Kecepatan dari mesin pelontar ini adalah kecepatan maksimum dari semua roda gigi yang dipasang.
Sebagai tambahan, mesin pelontar ini tidak bisa menembak dengan sudut yang lebih besar dari 180 derajat. Artinya konfigurasi mesin yang menyebabkan hal tersebut terjadi tidak diperbolehkan. Perlu diperhatikan pula bahwa nilai pemain didapat dari jauhnya jarak. Artinya arah tembak dapat diabaikan (sudut kurang dari 90 derajat memiliki arah tembak berlawanan dengan sudut lebih dari 90 derajat). Jumlah roda gigi yang ada bersifat terbatas, artinya pemain hanya dapat memakai tiap roda gigi maksimal sekali saja.
Untuk membantu, berikut adalah rumus untuk menghitung jarak tembak X pada permainan Rocket Duck, diberikan nilai sudut a dan kecepatan awal V0.
Bantulah Kwek dan Kwak memilih konfigurasi roda gigi optimal, untuk mendapatkan jarak terjauh.
Format Masukan
Pada baris pertama, 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, atau 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 adalah bilangan N yang menyatakan banyaknya pilihan roda gigi yang tersedia.
N baris berikutnya terdiri dari dua angka Ki dan Si, yang menyatakan nilai kecepatan dan nilai sudut dari roda gigi yang bersesuaian. Nilai sudut diberikan dengan skala perbesaran 10× lipat sehingga nilai sudut 900 maksudnya adalah 90 derajat, nilai sudut 135 maksudnya adalah 13,5 derajat, dan sebagainya.
Format Keluaran
Untuk tiap kasus uji, keluarkan sebuah bilangan riil hingga 12 angka di belakang penanda desimal yang menyatakan jarak terjauh yang dapat dicapai dengan konfigurasi roda gigi optimal. Perbedaan perhitungan absolut atau perhitungan relatif di bawah 0,001 akan diterima.
Contoh Masukan
0..3.567
3
50 160
105 320
101 290
Contoh Keluaran
107453.118185065090
Subsoal
Pada semua subsoal, berlaku:
- 1 ? Si ? 1.800
- Ki dan Si adalah bilangan bulat.
Subsoal 1 (8 poin)
- N = 5
- 1 ? Ki ? 100
- Nilai K tiap roda gigi adalah sama.
- Kasus uji dapat diunduh di sini.
Subsoal 2 (10 poin)
- N = 5
- 1 ? Ki ? 100
- Kasus uji dapat diunduh di sini.
Subsoal 3 (13 poin)
- 1 ? N ? 10
- 1 ? Ki ? 100
Subsoal 4 (14 poin)
- 1 ? N ? 50
- 1 ? Ki ? 100
- Nilai K tiap roda gigi adalah sama.
Subsoal 5 (15 poin)
- 1 ? N ? 50
- 1 ? Ki ? 100
Subsoal 6 (19 poin)
- 1 ? N ? 1.000
- 1 ? Ki ? 1.000
Subsoal 7 (21 poin)
- 1 ? N ? 500.000
- 1 ? Ki ? 1.000
5.
1s, 256MB
Hari ini Pak Dengklek ingin mengecat rumahnya dengan warna favorit bebek-bebeknya. Karena Pak Dengklek hanya memiliki kaleng-kaleng cat dengan warna dasar (merah, kuning, dan biru), maka Pak Dengklek menyiapkan sebuah ember dengan kapasitas maksimal 1.000 cc untuk mencampurkan ketiga warna dasar tersebut menjadi warna favorit bebek-bebeknya.
Pada suatu waktu, Pak Dengklek dapat menambahkan suatu warna dasar sebanyak sejumlah cc ke dalam embernya kemudian mencampurkannya. Perlu diperhatikan bahwa campuran warna tersebut tidak boleh melebihi kapasitas ember. Karena cat yang dipakai Pak Dengklek mudah mengering, maka Pak Dengklek hanya dapat melakukan proses menambahkan dan mencampurkan ini maksimal sebanyak 100 kali. Setelah melakukan proses menambahkan dan mencampurkan ini, campuran warna di ember akan dipakai untuk mengecat rumah.
Warna favorit bebek-bebek Pak Dengklek didapat dengan mencampurkan M cc warna Merah, K cc warna Kuning, dan B cc warna Biru dengan ketentuan M + K + B = 1.000. Perlu diperhatikan bahwa nilai M, K, dan B tidak dijamin berupa bilangan bulat.
Sayangnya, bebek-bebek Pak Dengklek tidak mengetahui nama dari warna favorit mereka sehingga mereka hanya dapat memberi tahu nilai kemiripan antara warna favorit mereka dengan warna yang berada pada ember Pak Dengklek. Nilai kemiripan tersebut dihitung dengan ketentuan berikut:
Dimisalkan campuran warna di ember Pak Dengklek saat ini yaitu X cc warna merah, Y cc warna Kuning, dan Z cc warna Biru.
Jarak warna antara warna di ember Pak Dengklek dengan warna favorit Bebek (W) dihitung dengan meminimalkan nilai (|kX - M| + |kY - K| + |kZ - B|) untuk suatu nilai riil k.
Sebagai catatan, pasti setidaknya ada satu dari ketiga nilai |kX - M|, |kY - K|, atau |kZ - B| yang sama dengan nol untuk mendapatkan nilai W.
Nilai kemiripan (F) dihitung dengan formula:
Sebagai contoh, apabila nilai M, K, dan B berturut-turut bernilai 200, 600, dan 200; serta nilai X, Y, dan Z berturut-turut bernilai 125, 200, dan 50; maka:
Untuk mendapatkan nilai W, perhatikan bahwa salah satu dari ketiga nilai adalah 0.
Apabila nilai |kX - M| = 0, maka k = 1,6. Sehingga nilai (|kX - M| + |kY - K| + |kZ - B|) = 400.
Apabila nilai |kY - K| = 0, maka k = 3. Sehingga nilai (|kX - M| + |kY - K| + |kZ - B|) = 225.
Apabila nilai |kZ-B| = 0, maka k = 4. Sehingga nilai (|kX - M| + |kY - K| + |kZ - B|) = 500.
Nilai W adalah nilai minimum dari ketiganya, sehingga W = 225.
Nilai F dihitung dengan formula F = 40.
Sehingga pada setiap Pak Dengklek melakukan proses menambahkan dan mencampurkan (yang telah dijelaskan pada paragraf 2), bebek-bebek Pak Dengklek akan memberi tahu nilai F kepada Pak Dengklek.
Bantulah Pak Dengklek untuk mengecat rumahnya dengan warna semirip mungkin dengan warna favorit bebek-bebeknya, yaitu mendapatkan nilai F sebesar mungkin!
Format Interaksi
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, atau 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.
Selama interaksi berlangsung, program Anda diharuskan mencetak salah satu dari dua perintah: TAMBAH [WARNA] [TAKARAN] dan SELESAI.
Cetaklah TAMBAH [WARNA] [TAKARAN], jika Anda hendak menambahkan [TAKARAN] cc cat berwarna [WARNA] ke dalam ember. Volume cairan setelah ditambahkan tidak boleh melebihi kapasitas ember yakni 1.000 cc dan merupakan bilangan riil positif dengan 4 angka di belakang koma. Warna yang boleh ditambahkan hanyalah warna MERAH, KUNING, atau pun BIRU. Perhatikan bahwa perintah ini hanya dapat dipanggil maksimal 100 kali. Setelah mencetak perintah ini, program anda akan menerima input sebuah bilangan riil F persen dengan 4 angka di belakang koma sesuai dengan deskripsi soal.
Cetaklah SELESAI, jika Anda hendak menyelesaikan proses menambahkan dan mencampurkan. Campuran cat yang berada di dalam ember akan digunakan Pak Dengklek untuk mengecat rumahnya. Setelah mencetak perintah ini, interaksi akan selesai dan penilaian akan dilakukan.
Contoh Interaksi
|
Keluaran Program Peserta |
Umpan Balik Grader (Bebek) |
Informasi Tambahan |
|---|---|---|
| 0..3 | ||
| TAMBAH MERAH 100.0000 | ||
| 0.0000 | W = 800.0000 | |
| TAMBAH KUNING 123.4500 | ||
| 11.8159 | W = 486.0267 | |
| TAMBAH KUNING 76.5500 | ||
| 30.7180 | W = 300.0000 | |
| TAMBAH BIRU 50.0000 | ||
| 51.0102 | W = 150.0000 | |
| TAMBAH MERAH 25.0000 | ||
| 40.0000 | W = 225.0000 | |
| SELESAI | ||
| (interaksi selesai) | |
Penjelasan Contoh Interaksi
Pada kasus tersebut, nilai M, K, dan B berturut-turut bernilai 200, 600, dan 200.
Pada akhirnya, warna yang digunakan Pak Dengklek untuk mengecat rumahnya merupakan campuran dari :
X = 125 cc warna Merah,
Y = 200 cc warna Kuning, dan
Z = 50 cc warna Biru.
Nilai yang didapatkan peserta adalah nilai F terakhir yaitu 40.
Subsoal
Tidak ada subsoal pada soal ini. Poin total yang Anda peroleh adalah akumulasi nilai dari 100 buah kasus uji. Semua kasus uji akan termasuk di dalam setidaknya 1 dari 3 himpunan kasus uji berikut.
Himpunan Kasus Uji 1 (20 kasus uji)
- M = K
- Nilai M, K, dan B adalah sebuah bilangan bulat.
Himpunan Kasus Uji 2 (30 kasus uji)
- B = 500
- Nilai M, K, dan B tidak dipastikan sebuah bilangan bulat.
Himpunan Kasus Uji 3 (50 kasus uji)
- Nilai M, K, dan B tidak dipastikan sebuah bilangan bulat.
Untuk membantu Anda memahami interaksi, disediakan game yang dapat diakses di sini. Kasus uji yang diberikan pada game ini hanyalah untuk visualisasi dan tidak termasuk dalam penilaian seperti pada game di soal interaktif sebelumnya.
6.
1s, 32MB
Pak Dengklek bersama tim risetnya sedang mengembangkan program untuk mereduksi pesan yang berupa sederetan huruf alfabet kapital (A – Z). Program ini sudah selesai dikembangkan, dan kini memasuki tahap pengujian. Sayangnya, Pak Dengklek dan tim kebingungan bagaimana memastikan bahwa program yang mereka kembangkan bekerja dengan baik. Akhirnya ia meminta bantuan Anda untuk membuat program yang dapat membantu mengoreksi pekerjaan Pak Dengklek.
Program yang diinginkan Pak Dengklek sederhana. Anda akan diberikan sebuah untaian pesan berisi simbol A – Z (semua kapital) tanpa spasi. Setiap huruf akan dinomori 1 sampai N, dengan N adalah panjang dari pesan itu sendiri. Kemudian Pak Dengklek akan memberikan beberapa pertanyaan yang dinyatakan oleh pasangan bilangan i dan j. Program anda harus mengeluarkan hasil reduksi substring dari posisi ke-i hingga posisi ke-j. Adapun aturan reduksi yang diinginkan adalah sebagai berikut:
Untuk setiap sekumpulan huruf yang saling bersebelahan dan memiliki simbol yang sama, hapus semua kecuali satu. Dengan kata lain, pada hasil reduksi pesan, tidak ada dua huruf yang sama akan saling bersebelahan. Contoh: HAALLLLLOOOOO ? HALO, MATARAM ? MATARAM, dan AAAAA ? A.
Hitung panjang pesan setelah dilakukan proses reduksi. Keluarkan angka ini, karena ini merupakan informasi yang penting untuk Pak Dengklek. Contoh: HAALLLLLOOOOO ? HALO (4 huruf).
Jika panjang pesan yang tereduksi lebih kecil dari 10, cetak juga pesan hasil reduksi tersebut.
Bisakah Anda menyelesaikan program yang diinginkan Pak Dengklek? Sebagai catatan, Pak Dengklek hanya memberikan Anda sedikit waktu karena sebentar lagi hasil penelitian mereka akan dipublikasikan.
Format Masukan
Pada baris pertama, 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, atau 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 2 bilangan, N dan Q, dimana N adalah panjang pesan dan Q adalah banyaknya pertanyaan.
Baris berikutnya adalah sebuah pesan yang terdiri dari simbol A – Z, sepanjang N.
Q baris berikutnya berisi 2 buah bilangan i dan j.
Format Keluaran
Untuk setiap pertanyaan, keluarkan panjang pesan setelah melakukan reduksi potongan pesan dari posisi ke-i hingga posisi ke-j. Apabila panjang pesan lebih kecil dari 10, maka tampilkan hasil reduksinya di baris yang sama dipisahkan oleh spasi.
Contoh Masukan
0..345
20 5
AAABBCCCCCQWERTYUIOP
1 1
1 3
2 9
1 20
18 20
Contoh Keluaran
1 A
1 A
3 ABC
13
3 IOP
Subsoal
Subsoal 1 (7 poin)
- N = 15
- Q = 10
- Kasus uji dapat diunduh di sini.
Subsoal 2 (11 poin)
- N = 100
- Q = 10
- Kasus uji dapat diunduh di sini.
Subsoal 3 (21 poin)
- 1 ? N ? 100
- 1 ? Q ? 100
Subsoal 4 (27 poin)
- 1 ? N ? 100
- 1 ? Q ? 100.000
Subsoal 5 (34 poin)
- 1 ? N ? 100.000
- 1 ? Q ? 100.000
7.
0.5s, 64MB
Perang dunia ketiga sudah pecah! Kedamaian di Negara Bebek pun terancam. Pak Dengklek yang sangat cinta Negara Bebek pun membuat sebuah senjata canggih yang menggunakan teknologi laser dan diyakini mampu menghancurkan musuh sekuat apapun.
Senjata canggih Pak Dengklek memiliki sebuah layar dan 3 tombol:
Layar: Untuk menampilkan kekuatan laser saat ini (harus selalu berupa bilangan asli).
Tombol "Tembak": Untuk menembakkan laser ke musuh.
Tombol "Kali 2": Membuat laser menjadi 2 kali lebih kuat dari sebelumnya.
Tombol "Bagi 2": Membuat kekuatan laser menjadi setengah dari sebelumnya. Jika kekuatan laser sebelum dilakukan operasi ini berupa bilangan ganjil, maka tidak terjadi apa-apa.
Nilai awal kekuatan laser hanya dapat diatur sekali sebelum pasukan musuh datang, karena untuk mengganti kekuatan laser membutuhkan waktu yang sangat lama (kecuali menggunakan tombol "Kali 2" dan tombol "Bagi 2"). Perhatikan bahwa nilai awal kekuatan laser ini harus lebih dari 0.
Senjata laser buatan Pak Dengklek ini tentunya menggunakan daya yang sangat besar. Pak Dengklek berkata bahwa untuk setiap satuan kekuatan laser yang ditembakkan menggunakan 1 unit energi. Tentunya kekuatan setiap pasukan musuh berbeda-beda, sehingga kekuatan laser yang diperlukan untuk menghancurkan mereka pun bisa jadi berbeda-beda. Untungnya, BINB (Badan Intelijen Negara Bebek) sudah mengetahui kekuatan musuh yang akan menyerang Negara Bebek dan sudah menghitung kekuatan laser yang diperlukan untuk menghancurkan masing-masing musuh.
Diberikan kekuatan laser minimum yang dibutuhkan untuk menghancurkan pasukan-pasukan negara musuh, berapa minimal unit energi yang harus terbuang untuk menghancurkan seluruh pasukan musuh? Anda harus menentukan nilai awal kekuatan laser, yang boleh ditentukan secara bebas.
Unit energi yang terbuang untuk menghancurkan satu pasukan musuh didefinisikan sebagai selisih dari unit energi minimal untuk menghancurkan pasukan tersebut dan unit energi yang digunakan Negara Bebek untuk menghancurkan pasukan tersebut. Sedangkan unit energi yang terbuang untuk menghancurkan seluruh musuh adalah jumlah dari unit energi yang terbuang untuk setiap pasukan musuh.
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, atau 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 pada berkas masukan berisi sebuah bilangan bulat N yang menyatakan banyaknya pasukan musuh yang akan menyerang Negara Bebek.
Baris ketiga berisi N buah bilangan bulat non-negatif Xi yang menyatakan kekuatan laser minimum untuk menghancurkan pasukan ke-i.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yang menyatakan unit energi yang terbuang minimal yang diperlukan untuk menghancurkan semua pasukan musuh.
Contoh Masukan 1
0..3456
2
7 31
Contoh Keluaran 1
2
Contoh Masukan 2
0..3456
3
4 8 2
Contoh Keluaran 2
0
Subsoal
Subsoal 1 (11 poin)
- N = 10
- Xi = i
- Kasus uji dapat diunduh di sini.
Subsoal 2 (7 poin)
- N = 12
- 0 ? Xi ? 10
- Kasus uji dapat diunduh di sini.
Subsoal 3 (23 poin)
- 1 ? N ? 100
- 0 ? Xi ? 100
Subsoal 4 (12 poin)
- 1 ? N ? 3.000
- 0 ? Xi ? 3.000
Subsoal 5 (31 poin)
- 1 ? N ? 100.000
- 0 ? Xi ? 100.000
Subsoal 6 (16 poin)
- 1 ? N ? 1.000.000
- 0 ? Xi ? 1.000.000
8.
0.4s, 256MB
Pak Dengklek memiliki sebuah kebun yang panjangnya tak hingga. Kebun Pak Dengklek dapat direpresentasikan dalam garis sumbu x pada koordinat Kartesian. Pak Dengklek memiliki N ekor bebek pada kebun tersebut. Bebek ke-i terletak pada koordinat xi pada sumbu x, dengan xi adalah bilangan bulat. Dijamin tidak ada dua bebek pada posisi yang sama.
Sepasang bebek dapat berkomunikasi jika dan hanya jika tidak ada bebek lain yang berada di antara dua bebek tersebut. Karena N bebek semuanya berada pada satu garis, tentu saja ada N - 1 pasang bebek yang dapat berkomunikasi. Jarak dari sebuah komunikasi adalah jarak dua bebek yang sedang melakukan komunikasi tersebut.
Sebagai contoh, jika pada awalnya ada 4 bebek yang berada pada posisi {1, 2, 5, 6}, maka jarak komunikasi bebek 1 dan 2 adalah 1, jarak komunikasi bebek 2 dan 3 adalah 3, dan jarak komunikasi bebek 3 dan 4 adalah 1.
Pada suatu saat mungkin saja terdapat jarak komunikasi yang berbeda-beda. Pak Dengklek merasa komunikasi bebek berjalan tidak lancar jika terdapat lebih dari satu nilai jarak komunikasi. Untuk itu, Pak Dengklek mungkin harus mengganti konfigurasi kebunnya. Bebek-bebek Pak Dengklek sudah terlalu nyaman dengan posisinya, sehingga mereka tidak mau dipindah posisinya. Sehingga, yang bisa dilakukan oleh Pak Dengklek adalah menambahkan bebek baru ke kebun atau mengambil bebek lama keluar dari kebun.
Pak Dengklek akan mengambil X bebek dan meletakkan Y bebek, sehingga pada akhirnya terdapat (N - X + Y) bebek, dan posisi bebek-bebek tersebut harus berbeda-beda dan bebek ke-i terletak pada xi’ dimana xi’ adalah bilangan bulat, dan semua jarak komunikasi untuk (N - X + Y - 1) pasangan bebek bernilai sama. Tentukan nilai X + Y minimal yang dapat dilakukan oleh Pak Dengklek.
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, atau 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 menunjukkan banyaknya bebek mula-mula.
Baris ketiga berisi N bilangan bulat yang dipisahkan spasi. Bilangan ke-i menunjukkan nilai dari xi.
Format Keluaran
Sebuah bilangan bulat yang menunjukkan nilai X + Y minimal agar konfigurasi kebun Pak Dengklek memenuhi ketentuan di atas.
Contoh Masukan
0..3456
5
2 4 6 10 18
Contoh Keluaran
2
Subsoal
Pada semua subsoal, berlaku:
- -2.500 ? xi ? 2.500
Subsoal 1 (6 poin)
- N = 6
- Kasus uji dapat diunduh di sini.
Subsoal 2 (14 poin)
- N = 9
- Kasus uji dapat diunduh di sini.
Subsoal 3 (19 poin)
- 1 ? N ? 15
Subsoal 4 (21 poin)
- 1 ? N ? 50
Subsoal 5 (13 poin)
- 1 ? N ? 300
Subsoal 6 (27 poin)
- 1 ? N ? 2.000
9.
1s, 64MB
Kwik adalah bebek Pak Dengklek yang senang menonton TV. Salah satu film favoritnya adalah serial “The Indiana Duck”. Serial ini mengisahkan seekor bebek yang bekerja sebagai arkeologi dan menemukan harta karun historis di seluruh dunia. Indiana Duck terkenal dengan atribut legendarisnya berupa topi koboi dan cambuk untuk membela diri dari serangan musuh.
Pada suatu hari, Kwik menemukan peta harta karun dalam kotak kecil di salah satu sudut gudang Pak Dengklek. Dalam peta itu tertulis jika seseorang mendaki turun melalui sumur tua di belakang gudang, maka ia akan menemui gua raksasa berukuran R × C dengan lautan magma di bawahnya. Dari dasar lautan magma tersebut menyembul beberapa bongkahan batu keras yang dapat digunakan sebagai pijakan. Pada salah satu bongkahan batu terdapat harta karun yang sudah dijaga selama beberapa generasi keluarga Dengklek. Kwik sangat senang karena dia bisa berlagak meniru Indiana Duck tokoh idolanya.
Satu-satunya cara untuk berpindah dari suatu bongkahan batu ke bongkahan batu lainnya adalah dengan melompat (Kwik tidak boleh menyentuh lautan magma jika ingin kembali hidup-hidup). Selama berada dalam suatu bongkahan batu, Kwik dapat menjelajahi bongkahan batu tersebut tanpa perlu melompat (misalnya, untuk berpindah ke sisi lain kemudian baru melompat). 2 petak batu akan membentuk sebuah bongkahan batu besar jika kedua petak batu tersebut berbagi sisi.
Karena Kwik masih kecil, dia tidak dapat melakukan gerakan yang sulit. Kwik hanya bisa melompat untuk menyeberangi lautan magma secara garis lurus (tidak dapat berbelok di udara). Kwik juga hanya dapat melompat ke arah utara, timur, selatan, atau barat. Karena perjalanan panjang, Kwik akan menghemat tenaganya dan akan selalu mendarat di bongkahan batu terdekat yang ditemuinya di arah lompatan.
Kwik berencana mendapatkan harta karun yang disebutkan dalam peta Kwik pun menceritakan rencana hebatnya kepada Anda dan meminta agar Anda tidak melapor ke Pak Dengklek. Anda sangat khawatir dengan keselamatan Kwik, namun Anda juga tidak bisa menemani Kwik dalam petualangannya karena Anda tidak ingin ketinggalan acara “Duck’s Got Talent”. Karena itu Anda hendak membantu Kwik dengan menentukan berapa lompatan minimal yang harus dilakukan Kwik agar dapat sampai ke harta karun (tentunya, semakin sedikit melompat akan menghemat energi Kwik dan menjamin keselamatannya).
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, atau 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 dalam berkas masukan berisi 2 buah bilangan R dan C yang dipisahkan oleh tepat sebuah spasi. R baris berikutnya berisi C buah karakter yang menyatakan konfigurasi petak batu dan lokasi harta karun sesuai deskripsi dalam peta. Sebuah petak dalam gua raksasa tersebut hanya dapat berupa salah satu dari kemungkinan karakter di bawah ini.
‘#’ : petak tersebut merupakan petak batu yang bisa diinjak.
‘.’ : petak tersebut merupakan lautan magma yang tidak boleh diinjak.
‘S’ : petak ini merupakan bagian akhir dari tangga pada sumur, atau dengan kata lain tempat Kwik memulai petualangannya. Petak ini pasti merupakan bagian dari petak batu yang bisa diinjak.
‘T’ : petak ini tempat harta karun yang dimaksud. Petak ini pasti merupakan bagian dari petak batu yang diinjak.
Format Keluaran
Cetak sebuah bilangan dalam 1 baris yang menyatakan berapa banyak lompatan paling sedikit yang harus dilakukan Kwik agar dapat sampai ke petak harta karun. Cetak -1 jika Kwik tidak akan pernah menemukan harta karun.
Contoh Masukan
0....56
7 7
#....#T
#..#...
..##..#
...#..#
.#.#..#
.#..S..
.#..#..
Contoh Keluaran
4
Subtask
Pada semua subsoal, berlaku:
- Banyaknya bongkahan batu tidak melebihi 1.000.
Subsoal 1 (11 poin)
- R = 12
- C = 12
- Semua bongkahan batu terdiri dari tepat satu petak batu.
- Berkas kasus uji bisa diunduh di sini.
Subsoal 2 (8 poin)
- R = 12
- C = 12
- Berkas kasus uji bisa diunduh di sini.
Subsoal 3 (18 poin)
- 1 ? R, C ? 100
- Semua bongkahan batu terdiri dari tepat satu petak batu.
Subsoal 4 (21 poin)
- 1 ? R, C ? 100
- Semua bongkahan batu berbentuk persegi panjang.
Subsoal 5 (26 poin)
- 1 ? R, C ? 100
Subsoal 6 (16 poin)
- 1 ? R, C ? 1.000
10.
1s, 32MB
Tahukah anda apa itu suten? Suten, sut, suit (suwit), atau pingsut adalah cara mengundi untuk dua orang dengan cara mengadu jari untuk menentukan siapa yang menang.
Di Indonesia, jari yang dipergunakan dalam suten adalah ibu jari yang diumpamakan sebagai gajah, jari telunjuk yang diumpamakan sebagai manusia, dan jari kelingking yang diumpamakan sebagai semut. Dua orang yang bersuten secara serentak mengacungkan jari yang dipilihnya. Hasilnya seri terjadi bila kedua belah pihak yang bersuten mengacungkan jari yang berkekuatan sama, misalnya: kelingking melawan kelingking. Biasanya, apabila terjadi seri maka suten diulang hingga ada pihak yang menang, namun peraturan ini tidak berlaku untuk saat ini.
Jari yang menjadi pemenang suten:
Ibu jari versus telunjuk: pemenang adalah ibu jari.
Telunjuk versus kelingking: pemenang adalah telunjuk.
Kelingking versus ibu jari: pemenang adalah kelingking.
Anda, sebagai salah satu finalis OSN Komputer 2014, diminta untuk menyelesaikan tantangan berikut.
Ada N anak yang bermain suten bersama-sama. Anak-anak ini memiliki jari favorit mereka masing-masing sehingga setiap melakukan suten, mereka selalu mengeluarkan jari favoritnya untuk diadu. Setiap anak melakukan suten dengan anak lainnya tepat sekali, sehingga ada (N × (N - 1)) / 2 buah pertandingan suten yang akan dilakukan.
Diberikan nilai N, Anda (dan program Anda) akan ditanyakan (N × (N - 1)) / 2 buah pertandingan suten dan menentukan siapa pemenangnya (atau menentukan adanya seri). Apabila Anda salah menjawab, maka secara otomatis Anda gagal menyelesaikan tantangan dan akan mendapatkan nilai 0.
Karena Anda tidak mengetahui jari favorit masing-masing anak, Anda diperbolehkan untuk memilih PASS atau memilih untuk tidak menjawab sebuah pertandingan. Apabila Anda memilih untuk PASS, maka anda akan diberikan hasil pertandingan tersebut. Anda diminta untuk memilih PASS sesedikit mungkin, dengan kata lain Anda diminta untuk menjawab setiap hasil pertandingan sebanyak mungkin.
Format Interaksi
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.
Kemudian, program Anda akan menerima input sebuah bilangan N yaitu banyaknya anak yang bermain suten. Kemudian, sebanyak (N × (N - 1)) / 2 kali program Anda akan menerima input 2 buah bilangan X dan Y yang menandakan pertandingan suten antara anak ke-X dan anak ke-Y. Anda diminta untuk mencari tahu hasil pertandingan suten tersebut satu per satu.
Keluaran yang dapat Anda keluarkan adalah:
Apabila pertandingan suten dimenangkan oleh anak ke-Z, program Anda diminta untuk mengeluarkan output Z MENANG.
Apabila pertandingan suten berlangsung seri, program Anda diminta untuk mengeluarkan output SERI.
Apabila Anda memilih untuk PASS atau tidak menjawab, program Anda diminta untuk mengeluarkan output PASS. Apabila memilih PASS, maka program Anda akan menerima hasil pertandingan suten tersebut dalam bentuk Z MENANG ataupun SERI.
Contoh Interaksi
| Keluaran Program Peserta | Umpan Balik Grader |
|---|---|
| 0....567 | |
| 4 | |
| 1 2 | |
| SERI | |
| 1 3 | |
| 3 MENANG | |
| 1 4 | |
| 1 MENANG | |
| 2 3 | |
| PASS | |
| 3 MENANG | |
| 2 4 | |
| PASS | |
| 2 MENANG | |
| 3 4 | |
| 4 MENANG | |
| (interaksi selesai) |
Subsoal
Pada semua subsoal, berlaku:
- 3 ? N ? 100
- Dimisalkan P adalah banyaknya PASS paling banyak yang boleh dilakukan peserta.
Subsoal 1 (6 poin)
- N = 5
- P = 6
- Untuk setiap pertandingan, berlaku X < Y.
- Input pertandingan akan diurutkan dengan aturan berikut:
- Pertandingan diurut mula-mula dari nilai X terkecil.
- Apabila 2 buah pertandingan memiliki nilai X yang sama, maka diurut mula-mula dari nilai Y terkecil.
Subsoal 2 (12 poin)
- N = 8
- P = 7
Khusus untuk subsoal 1 dan subsoal 2:
- Hanya terdapat sebuah kasus uji (satu subsoal dinyatakan oleh satu kasus uji), yang dapat dimainkan di sini.
- Anda boleh memainkan permainan ini berulang kali tanpa mendapatkan penalti.
- Jika Anda sudah memenangkan permainan untuk subsoal tertentu, Anda dapat memilih pilihan pada permainan untuk mengeluarkan source code yang dapat langsung Anda kirimkan ke grader dan menjawab dengan benar pada subsoal yang telah Anda menangkan.
- Anda tidak diwajibkan memainkan permainan ini untuk mengerjakan kedua subsoal ini. Anda diperbolehkan untuk menulis kode Anda sendiri untuk mengerjakan kedua subsoal ini.
Subsoal 3 (8 poin)
- N = 3
- P = 2
Subsoal 4 (13 poin)
- P = (N × (N - 1)) / 2 - N + 2
Subsoal 5 (14 poin)
- P = N - 1
- Untuk setiap pertandingan, berlaku X < Y
- Input pertandingan akan diurutkan dengan aturan berikut:
- Pertandingan diurut mula-mula dari nilai X terkecil.
- Apabila 2 buah pertandingan memiliki nilai X yang sama, maka diurut mula-mula dari nilai Y terkecil.
Subsoal 6 (19 poin)
- P = N - 1
- Untuk N - 1 pertandingan pertama, berlaku X < Y.
- Untuk N - 1 pertandingan pertama, pada pertandingan ke-i nilai Y = i + 1.
Subsoal 7 (28 poin)
- P = N - 1
11.
Untuk menyambut OSN 2014, Pak Dengklek berencana membuat sebuah hiasan dinding di laboratorium tempat Bidang Informatika dilaksanakan. Hiasan ini cukup sederhana, yakni hanya terdiri atas paku-paku dan untaian tali. Pak Dengklek memiliki N buah paku untuk membuat hiasan ini. Paku-paku ini dinomori secara unik dari 1 sampai dengan N.
Cara membuat hiasan dinding ini adalah sebagai berikut. Mula-mula, Pak Dengklek membariskan paku-paku tersebut dalam sebuah barisan. Lalu, Pak Dengklek memasang paku pertama pada dinding. Untuk setiap paku kedua sampai dengan ke-N secara berurutan, Pak Dengklek melakukan langkah-langkah berikut:
Tinjau paku paling atas pada dinding.
Misalkan X = paku yang sedang ditinjau, dan Y = paku yang ingin dipasang.
a. Jika nomor dari Y < nomor dari X:
(i) Jika X tidak memiliki paku yang terhubung dengan tali di sebelah kiri bawahnya, pasang Y persis di
sebelah kiri bawah X, dan hubungkan keduanya menggunakan tali. Pemasangan paku dianggap selesai.
(ii) Jika X memiliki paku yang terhubung dengan tali di sebelah kiri bawahnya, tinjau paku tersebut dan
kembali ke Langkah 2.
b. Jika nomor dari Y > nomor dari X:
(i) Jika X tidak memiliki paku yang terhubung dengan tali di sebelah kanan bawahnya, pasang Y persis di
sebelah kanan bawah X, dan hubungkan keduanya menggunakan tali. Pemasangan paku dianggap selesai.
(ii) Jika X memiliki paku yang terhubung dengan tali di sebelah kanan bawahnya, tinjau paku tersebut dan
kembali ke Langkah 2.
Sebagai contoh, misalkan Pak Dengklek ingin memasang paku keenam bernomor 8. Berikut adalah ilustrasi langkah-langkah pemasangan paku ini:
Pak Dengklek sudah memiliki sebuah desain hiasan dinding yang dibuat oleh panitia dekorasi. Ia ingin segera memasang paku-paku agar terbentuk hiasan dinding tersebut. Tentu saja, mula-mula ia harus membariskan paku-paku tersebut. Mungkin saja ada lebih dari satu kemungkinan barisan yang menghasilkan hiasan dinding tersebut. Pak Dengklek, sebagai seorang yang senang dengan teka-teki logika, justru penasaran dengan pertanyaan berikut: jika barisan-barisan yang mungkin menghasilkan hiasan dinding tersebut diurutkan dengan urutan leksikografis, barisan apa yang berada pada posisi ke-K?
Catatan: barisan paku A lebih kecil daripada barisan paku B secara leksikografis, apabila pada posisi pertama di mana A dan B berbeda, nomor paku pada posisi tersebut di A lebih kecil daripada nomor paku pada posis tersebut di B.
Bantulah Pak Dengklek menjawab pertanyaan tersebut, agar ia dapat segera memasang paku-paku tersebut!
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 dua buah bilangan bulat N dan K. N-1 baris berikutnya mendeskripsikan sebuah desain hiasan dinding. Masing-masing baris berisi tiga buah bilangan bulat u, v, dan t:
Apabila t = 0, maka paku bernomor v terhubung dengan tali di sebelah kiri bawah dengan paku bernomor u.
Apabila t = 1, maka paku bernomor v terhubung dengan tali di sebelah kanan bawah dengan paku bernomor u.
Format Keluaran
Sebuah baris berisi barisan N buah bilangan, dipisahkan oleh spasi, yang menyatakan barisan nomor paku, sedemikian sehingga barisan ini merupakan barisan terkecil ke-K secara leksikografis.
Contoh Masukan 1
0..34.6
4 1
2 1 0
2 4 1
4 3 0
Contoh Keluaran 1
2 1 4 3
Contoh Masukan 2
0..3..6
4 3
2 1 0
2 4 1
4 3 0
Contoh Keluaran 2
2 4 3 1
Subsoal
Pada semua subsoal, berlaku:
- Setiap paku memiliki nomor unik antara 1 sampai dengan N.
- Masukan selalu merupakan desain hiasan dinding yang benar.
- K tidak lebih daripada banyaknya cara penyusunan hiasan dinding yang bersangkutan.
- Meskipun cara penyusunan hiasan dinding bisa banyak sekali, nilai K tidak akan lebih daripada 2.000.000.000.
Subsoal 1 (7 poin)
- N = 8
- K = 1
- Kasus uji dapat diunduh di sini.
Subsoal 2 (14 poin)
- N = 8
- K = 3
- Kasus uji dapat diunduh di sini.
Subsoal 3 (17 poin)
- 1 ? N ? 8
Subsoal 4 (11 poin)
- 1 ? N ? 100
- K = 1
Subsoal 5 (20 poin)
- 1 ? N ? 100
- Semua paku dengan nomor lebih kecil daripada nomor paku teratas tidak memiliki paku yang terhubung dengan tali di sebelah kanan bawah.
- Semua paku dengan nomor lebih besar daripada nomor paku teratas tidak memiliki paku yang terhubung dengan tali di sebelah kiri bawah.
Subsoal 6 (31 poin)
- 1 ? N ? 100