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

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