InternationalOlympiadinInformatics2017July28–August4,2017Tehran,IranDay2Tasks

prizeIndonesian(IDN)

HadiahAkbarHadiah Akbar adalah sebuah acara permainan televisi terkenal. Anda adalah peserta beruntungyangmajukebabakfinal.Andaberdirididepansebuahbarisberisi kotak,dinomoridari hingga

darikiri kekanan.Setiapkotakberisisebuahhadiahyang tidakdapatdilihatsampaikotaktersebutdibuka.Terdapat tipe hadiah berbeda. Tipe-tipe tersebut dinomori dari hinggadenganurutannilaimenurun.

Hadiahbertipe adalahhadiahyangpalingmahal:sebuahberlian.Terdapattepatsatuberlianpadakotak-kotak tersebut.Hadiahbertipe adalahhadiahyangpalingmurah:sebuahpermen lollipop.Untuk membuat permainan lebih menarik, banyaknya hadiah yang lebih murah jauh lebih besardaripadabanyaknyahadiahyanglebihmahal.Lebihjelasnya,untuksetiap sedemikiansehingga

kitamengetahuihalberikut: jika terdapat hadiahbertipe , terdapat lebihdarihadiahbertipe .

TujuanAndaadalahmendapatkanberlian tersebut.Padaakhir permainan,AndaharusmembukasebuahkotakdanAndaakanmendapatkanhadiahdidalamkotaktersebut.Sebelummemilihkotakyang harus dibuka, Anda dapat menanyakan beberapa pertanyaan kepada Rambod, pembawaacara dari permainan tersebut. Untuk setiap pertanyaan, Andamemilih sebuah kotak . Sebagaijawabannya,RambodakanmemberiAndasebuaharray berisiduabilanganbulat.Artinyaadalahsebagaiberikut:

Di antara kotak-kotak di sebelah kiri kotak , terdapat tepat kotak yang berisi sebuahhadiahyanglebihmahaldaripadahadiahpadakotak .Diantarakotak-kotakdisebelahkanankotak , terdapattepat kotakyangberisisebuahhadiahyanglebihmahaldaripadahadiahpadakotak .

Sebagai contoh, anggap . Sebagai pertanyaan Anda, Anda memilih kotak . Sebagaitanggapannya,RambodmemberitahuAndabahwa .Artidaritanggapaniniadalah:

Tepatsatudarikotak-kotak dan berisi sebuahhadiahyang lebihmahaldaripadahadiahpadakotak .Tepatduadarikotak-kotak berisisebuahhadiahyanglebihmahaldaripadahadiahpadakotak .

TugasAndaadalahmencarikotakyangberisiberliandenganmenanyakansedikitpertanyaan.

Detilimplementasi

Andaharusmengimplementasikanprosedurberikutini:

Prize (1 of 4)

intfind_best(intn)

Prosedurinidipanggiltepatsekaliolehgrader:banyaknyakotak.Prosedurtersebutharusmengembalikannomordarikotakyangberisiberlian,yakni,bilanganbulatunik ( )sedemikiansehinggakotak berisisebuahhadiahbertipe .

Prosedurdiatasdapatmemanggilprosedurberikut:

int[]ask(inti)

:nomordarikotakyangAndapilihuntukditanyakan.Nilaidari harusdiantara dan ,inklusif.Prosedur inimengembalikanarray berisi elemen.Disini, adalahbanyaknyahadiahyanglebihmahalpadakotak-kotakdisebelahkirikotak dan adalahbanyakhadiahyanglebihmahalpadakotak-kotakdisebelahkanankotak .

Contoh

Gradermelakukanpemanggilanprosedurberikut:

find_best(8)

Terdapat kotak. Anggap tipe-tipe hadiah adalah . Seluruh pemanggilanproseduraskyangmungkindannilaikembalianyangsesuaididaftarkandibawahini.

ask(0)mengembalikanask(1)mengembalikanask(2)mengembalikanask(3)mengembalikanask(4)mengembalikanask(5)mengembalikanask(6)mengembalikanask(7)mengembalikan

Pada contoh ini, berlian tersebut berada pada kotak . Maka prosedur find_best harusmengembalikan .

Prize (2 of 4)

Gambardiatasmengilustrasikancontohini.Bagianatasmenunjukkantipedarihadiahpadasetiapkotak.Bagianbawahmengilustrasikanpertanyaanask(2).Kotakyangditandaiberisihadiahyanglebihmahaldaripadahadiahpadakotak .

Batasan

.Tipedarihadiahpadasetiapkotakdiantara dan ,inklusif.Terdapattepatsatuhadiahbertipe .Untuk setiap , jika terdapat hadiah bertipe , terdapat lebih dari hadiahbertipe .

Subsoaldanpenilaian

Padabeberapakasusuji,perilakugraderadalahadaptif.Iniberartidalamkasus-kasusujiini,gradertidakmemilikisebuahbarisanhadiahyangtetap.Akantetapi,jawaban-jawabanyangdiberikanolehgrader dapatbergantungpadapertanyaan-pertanyaanyangditanyakanolehsolusiAnda.Dijaminbahwagrader menjawab sedemikian sehingga setelah setiap jawaban, terdapat setidaknya satubarisanhadiahyangkonsistendenganseluruhjawabanyangdiberikansejauhini.

1. (20poin)Terdapat tepat berliandan permen lollipop (sehingga, ).Andadapatmemanggilproseduraskpalingbanyak kali.

2. (80poin)Tidakadabatasantambahan.

Pada subsoal 2 Anda dapat mendapatkan sebuah nilai parsial. Anggap adalah banyaknyapemanggilanproseduraskmaksimumdiantaraseluruhkasusujipadasubsoalini.Maka,nilaiAndauntuksubsoalinidihitungberdasarkantabelberikutini:

Prize (3 of 4)

Pertanyaan Nilai

(dilaporkandiCMSsebagai'WrongAnswer')

Gradercontoh

Grader contoh tidakadaptif.Melainkan,grader contohhayamembacadanmenggunakansebuaharray tetap berisi tipe-tipe hadiah. Untuk setiap , tipe dari hadiah pada kotakdiberikansebagai .Gradercontohmengharapkanmasukandenganformatberikut:

baris :baris :

Grader contoh mencetak sebuah baris berisi nilai kembalian dari find_best dan banyaknyapemanggilanprosedurask.

Prize (4 of 4)