Black eyes and blue eyes P38218


Statement
 

pdf   zip

thehtml

To win the hand of his ladylove, Beremiz had to solve one last challenge in front of the Caliph. Five slave girls, each one covered with a veil, were presented to Beremiz. He was told that two of them had black eyes and always told the truth, while the other three slaves had with blue eyes and always lied. Beremiz should deduce the color of the eyes of all the slaves with only three questions.

Beremiz began by asking the first slave:

“What color are your eyes?”

Surprisingly, the answer was given in a dialect that was only understandable to the slaves. Considering the protest of Beremiz, the Caliph ordered that the rest of answers were given in Arabic. Despite the setback, Beremiz went on, and asked the second slave:

“¿What was the reply that your companion just gave?”

“She said: My eyes are blue.”

Finally, Beremiz asked the third slave:

“What color are the eyes of those two slaves that I have just questioned?”

“The first girl has black eyes and the second has blue eyes.”

After that answer, Beremiz deduced with certainty the color of the eyes of the five slaves (the first had black eyes, the second blue, the third black, and the last two blue), and so he won the hand of his beloved Telassim.

Input

Input consists of several cases, each with two natural numbers x and y between 0 and 104.

Output

Every case corresponds to a variant of the problem, where there are x slaves with black eyes and y slaves with blue eyes. You can only ask “Which is the color of the eyes of slave number i?” to the first slave, for all i between 1 and x + y.

Print the minimum number of questions needed to deduce the color of the eyes of each slave by using an optimal strategy, assuming the best and the worst luck in the answers. If it is impossible to tell no matter how many questions are asked, print “no”.

Public test cases
  • Input

    2 3
    1 1
    

    Output

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