Ojos negros y azules P38218


Statement
 

pdf   zip

thehtml

Para ganar la mano de su amada, Beremiz tuvo que resolver un último reto ante el califa. Se le presentaron cinco esclavas cubiertas con un velo, y se le dijo que dos tenían los ojos negros, y las otras tres los ojos azules. Además, las esclavas de ojos negros siempre decían la verdad, mientras que las de ojos azules siempre mentían. Beremiz debía deducir el color de los ojos de todas las esclavas con sólo tres preguntas.

Beremiz empezó preguntando a la primera esclava:

“¿De qué color son tus ojos?”

Sorprendentemente, la respuesta fue en un dialecto comprensible sólo para las esclavas. Ante la protesta de Beremiz, el califa ordenó que las siguientes respuestas fuesen en árabe. A pesar del contratiempo, Beremiz prosiguió, preguntando a la segunda esclava:

“¿Cuál fue la respuesta de tu compañera?”

“Su respuesta fue: Mis ojos son azules.”

Finalmente, Beremiz preguntó a la tercera esclava:

“¿De qué color son los ojos de las esclavas a las que he interrogado?”

“La primera tiene los ojos negros, y la segunda los tiene azules.”

Tras esa respuesta, Beremiz dedujo con certeza el color de los ojos de las cinco esclavas (la primera los tenía negros, la segunda azules, la tercera negros, y las dos últimas azules), y ganó así la mano de su amada Telassim.

Entrada

La entrada consiste en diversos casos, cada uno con dos naturales n y a entre 0 y 104.

Salida

Cada caso se corresponde con una variante del problema, sabiendo que hay n esclavas de ojos negros y a de ojos azules. Solamente se puede preguntar “¿De qué color son los ojos de la esclava número i?” a la primera esclava, para todo i entre 1 y n + a.

Escribid el mínimo número de preguntas necesarias para, usando una estrategia óptima, deducir el color de los ojos de cada esclava con la mejor y la peor de las suertes en las respuestas. Si no es posible deducirlo por muchas preguntas que se hagan, escribid “no”.

Public test cases
  • Input

    2 3
    1 1
    

    Output

    2 4
    no
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++