InternationalOlympiadinInformatics2017July28–August4,2017Tehran,IranDay2Tasks

prizeSpanish(COL)

ElGranPremioElGranPremioesun juegofamosodeTV.Ustedeselafortunadoconcursantequehaavanzadohastalarondafinal.Estáparadofrenteaunafilade cajas,numeradasdel al deizquierdaaderecha.Cadacajacontieneunpremioquenopuedeservistosinohastaquelacajaseaabierta.Existen tipos diferentes de premios. Los tipos son numerados del al en ordendescendentedevalor.

Elpremiodetipo eselmasvalioso:undiamante.Existeexactamenteundiamanteenlascajas.Elpremiodetipo eselmenosvalioso:unapaleta.Parahacereljuegomásemocionante,elnúmerode premios de bajo valor es mucho mayor que el número de premios más valiosos. Másconcretamente,paratodo talque sabemos losiguiente:siexisten premiosde tipo

,existenestrictamentemásde premiosdetipo .

Su objetivo es ganar el diamante.Al final del juego usted tendrá que abrir una caja y recibirá elpremioqueestacontiene.Antesdeelegirquécajaabrir,puedehacerleaRambod,elpresentadordel juego, algunas preguntas. Para cada pregunta, usted elige alguna caja . Como respuesta,Rambodledaráunarreglo conteniendodosenteros.

Susignificadoeselsiguiente:

Entrelascajasalaizquierdadelacaja hayexactamente cajasquecontienenunpremiomásvaliosoqueeldelacaja .Entre lascajasaladerechadelacaja hayexactamente cajasquecontienenpremiosmásvaliososqueeldelacaja .

Porejemplo,supongaque .Ensupregunta,ustedeligelacaja .Ramboldleresponde.Estarespuestasignificaque:

Exactamenteunadelascajas y contienenunpremiomásvaliosoqueeldelacaja .Exactamentedosdelascajas contienenunpremiomásvaliosoqueeldelacaja .

Su tareaesencontrar lacajaquecontieneeldiamantehaciendo lamenorcantidaddepreguntasposible.

Detallesdeimplementación

Debeimplementarelsiguienteprocedimiento:

intfind_best(intn)

Prize (1 of 4)

Esteprocedimientoesllamadoexactamenteunavezporelcalificador.:elnúmerodecajas.El procedimiento debe retornar el númerode la caja que contieneel diamante.Es decir, elúnicoentero talquelacaja contieneunpremiodetipo .

Elprocedimientoanteriorpuedehacerllamadasalsiguienteprocedimiento:

int[]ask(inti)

:elnúmerodelacajaporlaquedecidepreguntar.Elvalorde debeestarentre y ,inclusive.Esteprocedimientoretornaunarreglo con elementos.Aquí, eselnúmerodepremiosmás valiosos en las cajas a la izquierda de la caja y es el número de premiosmásvaliososenlascajasaladerechadelacaja .

Ejemplo

Elcalificadorhacelasiguientellamada:

find_best(8)

Hay cajas.Supongaque los tiposdepremiosson .Todos las llamadasposibles al procedimiento ask y sus correspondientes valores de retorno son listados acontinuación.

ask(0)retornaask(1)retornaask(2)retornaask(3)retornaask(4)retornaask(5)retornaask(6)retornaask(7)retorna

Enesteejemplo,eldiamanteseencuentraenlacaja .Porlotanto,elprocedimientofind_bestdeberetornar .

Prize (2 of 4)

Lafiguradearribailustraesteejemplo.Lapartesuperiormuestralostiposdelospremiosencadacaja. La parte inferior ilustra la pregunta ask(2). Las cajas marcadas contienen premios másvaliososqueeldecaja .

Restricciones

.Eltipodelpremioencadacajaseencuentraentre y ,inclusive.Existeexactamenteunpremiodetipo .Para todo , si existen premios de tipo , existenestrictamente más depremiosdetipo .

Subtareasypuntuación

Enalgunoscasosdepruebaelcomportamientodelcalificadoresadaptable.Estosignificaqueenestos casos de prueba el calificador no tiene una secuencia fija de premios. En su lugar, lasrespuestasdevueltasporelcalificadorpuedendependerdelaspreguntashechasporsusolución.Se garantiza que el calificador responde de talmanera que después de cada pregunta existe almenos una secuencia de premios consistente con todas las respuestas devueltas hasta esemomento.

1. (20 puntos) Existe exactamente diamante y paletas (por lo tanto, ). Puedellamaralprocedimientoaskalosumo veces.

2. (80puntos)Sinrestriccionesadicionales.

En lasubtarea2puedeobtenerunapuntuaciónparcial.Sea elmáximonúmerode llamadasalprocedimientoaskentretodosloscasosdepruebaenestasubtarea.Entonces,supuntuaciónparaestasubtareasecalculadeacuerdoalasiguientetabla:

Prize (3 of 4)

Preguntas Puntuación

(reportadaenCMScomo'WrongAnswer')

Calificadordeejemplo

Elcalificadordeejemplonoesadaptable.Ensu lugar,únicamente leeyusaunarreglo fijo detiposdepremios.Paratodo ,el tipodelpremioen lacaja esdadocomo .Elcalificadordeejemploesperaentradasenelsiguienteformato:

línea :línea :

Elcalificadordeejemploimprimeunasólalíneaquecontieneelvalorderetornodefind_bestyelnúmerodellamadasalprocedimientoask.

Prize (4 of 4)