InternationalOlympiadinInformatics2017July28–August4,2017Tehran,IranDay2Tasks

prizeRomanian(ROU)

TheBigPrizeJocul "Marelepremiu"esteun renumitshowde televiziune.Sunteținorocosulparticipantcares-acalificatînrundafinală.Stațiînfațaunuirândde cutii,numerotatedelastângaladreaptadelapână la . Fiecare cutie conține un premiu care nu poate fi văzut până când cutia nu estedeschisă.Există diferite tipuridepremii.Tipurile depremii sunt numerotatede la la înordineadescrescătoareavalorii.

Premiuldetipul estecelmaiscump:undiamant.Existăunsingurdiamantîncutii.Premiuldetipeste celmai ieftin: oacadea.Pentrua face jocul câtmai captivant, numărul premiilor ieftineestemultmaimaredecâtnumărulpremiilorscumpe.Maiexact,pentrutoate cu seștie:dacăexistă premiidetip ,atunciexistăstrictmaimultdecât premiidetipt.

Aveți scopul să câștigați diamantul. La sfârșitul jocului va trebui să deschideți cutia și să luațipremiuldincutie.ÎnaintedeadeschidecutiaaleasătrebuiesăîlîntrebațipeRambod,gazdashow-ului,câtevaîntrebări.Pentrufiecareîntrebare,vețialegeocutie .Carăspuns,Rambodvăvaoferiunșir careconținedoiîntregi.Semnificațiaacestorîntregieste:

Printrecutiiledinstângacutiei suntexact cutiicareconținpremiimaiscumpecapremiuldincutia .Printre cutiile din dreapta cutiei sunt exact cutii care conțin premii mai scumpe capremiuldincutia .

Deexemplu,presupunemcă șialegeticutia caîntrebarepusă.CarăspunsRambodvădășirul .Semnificațiaacestuirăspunseste:

Exactunadincutiile și conțineunpremiumaiscumpcapremiuldincutia .Exactdouădincutiile conținpremiimaiscumpecapremiuldincutia .

Sarcinavoastrăestesăgăsițicutiacareconținediamantulpunândunnumărmicdeîntrebări.

Detaliideimplementare

Trebuiesăimplementațiurmătoareaprocedură:

intfind_best(intn)

Aceastăprocedurăesteapelatăexactosingurădatadecătreevaluator.:număruldecutii.

Aceastăprocedurăreturneazănumărulcutieicareconținediamantul,adicăunîntregunic (

Prize (1 of 4)

)astfelîncâtcutia conținepremiuldetip .

Procedurademaisuspoateapelaurmătoareaprocedură:

int[]ask(inti)

:numărulcutieidesprecarevrețisă întrebați.Valoarea lui trebuiesă fie între și ,inclusiv.Aceastăprocedurăreturneazăunșir cu elemente. estenumărulpremiilormaiscumpedincutiiledinstângacutiei și estenumărulpremiilormaiscumpedincutiiledindreaptacutiei .

Exemplu

Evaluatorulexecutăurmătorulapelalprocedurii:

find_best(8)

Există cutii. Presupunemcăpremiile sunt de următoarele tipuri . Toatecazurileposibiledeapelaproceduriiaskșirespectivvalorilereturnatesunt:

ask(0)returneazăask(1)returneazăask(2)returneazăask(3)returneazăask(4)returneazăask(5)returneazăask(6)returneazăask(7)returnează

Înacestexemplu,diamantulesteîncutia .Deci,procedurafind_besttrebuiesăreturneze .

Prize (2 of 4)

Exemplul este ilustrat în figurademai sus.Parteadesusarată valorilepremiilor în fiecare cutie.Parteade josarată interogareaask(2).Cutiilemarcateconținpremiimaiscumpedecâtcutiacunumărul .

Restricțiișiprecizări

.Tipulpremiilorînfiecarecutieesteîntre și ,inclusiv.Existăunsingurpremiudetipul .Pentrutoate ,dacăexistă premiidetipul ,atunciexistăstrictmaimultdepremiidetipul .

Subtask-urișipunctaj

Înuneletestecomportamentulevaluatoruluiesteadaptiv.Adică,înacesteteste,evaluatorulnuareosecvență fixădepremii. În schimb, răspunsurile oferite de evaluator poate depindede întrebăriletransmisedesoluțiavoastră.Segaranteazăcăevaluatorul răspundeînașafel încâtdupăfiecarerăspunsexistăcelpuținosecvențăconsistentădepremiicutoaterăspunsuriledatepânăacum.

1. (20 puncte) Există exact diamant și acadele (prin urmare, ). Puteți apelaproceduraaskdecelmult ori.

2. (80puncte)Fărărestricțiiadiționale.

Însubtask-ul2putețiobțineunscorparțial.Fie numărulmaximdeapeluriaproceduriiaskpentrutoate testele din acest subtask. Punctajul pentru acest subtask este calculat conform următoruluitabel:

Prize (3 of 4)

Întrebări Punctaj

(raportatînCMSca'WrongAnswer')

Evaluatorlocal

Evaluatorul localnuesteadaptiv. Înschimb,elciteșteșiutilizeazăunșir fix de tipuridepremii.Pentru toate , tipul premiului din cutia este dat ca . Formatul intrării pentruevaluatorullocaleste:

linia :linia :

Evaluatorullocalafișeazăosingurăliniecareconținevaloareareturnatădefind_bestșinumăruldeapeluriaproceduriiask.

Prize (4 of 4)