Matcom Online Grader
MOG Round #26Ended |
D - Toros y Vacas
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
BitZero recientemente ha aprendido un juego nuevo y se lo ha mostrado a BitOne. Ambos coinciden en que el juego es realmente bello y deciden investigar cuáles son las mejores estrategias. Ahora ellos creen que saben jugar de manera óptima, o sea, que hacen siempre la jugada que minimice la cantidad de jugadas esperada para terminar el juego. Debemos aclarar aquí, que este problema iba a tratar sobre el último análisis que hizo BitOne sobre el juego de ajedrez, pero ha decidido ocultarlo y no hay nada que podamos hacer. Por eso, el juego del que hablamos es "Toros y Vacas". Si no has oído hablar de las reglas, te las presento muy rápidamente:
* El primer jugador escoge una secuencia de 4 números, cada uno entre 1 y 6 (incluidos). A esta secuencia la llamaremos solución.
* Las jugadas las realiza el segundo jugador.
* Una jugada consiste en hacer preguntas al primer jugador para obtener respuestas.
* Una pregunta es una secuencia de 4 números, cada uno entre 1 y 6 (incluidos).
* Una respuesta consiste en dos números: la cantidad de toros y la cantidad de vacas.
* Cada toro indica que la solución y la pregunta coinciden en una posición, esto es, existe una posición (entre 1 y 4) tal que la solución y la pregunta tienen el mismo número en ella.
* Cada vaca indica que existe un número en la pregunta que está en la solución, pero no en la misma posición.
* Para dar una respuesta, el primer jugador primero busca cuántos toros hay en la pregunta, y luego, usando solamente los números de la pregunta que no coinciden en posición con la solución, decide cuántas vacas hay en la pregunta.
* El juego termina cuando la pregunta coincide con la solución y por tanto la respuesta obtenida corresponde a exactamente 4 toros
Por ejemplo, si la solución es 4341, entonces estas son preguntas y respuestas posibles:
4222 1 toro 0 vacas
4422 1 toro 1 vaca
3451 1 toro 2 vacas
6134 0 toros 3 vacas
Las reglas pueden parecer algo complicadas, pero en realidad es un juego muy fácil de entender y es muy divertido.
Siempre debes ayudar a BitZero y BitOne, dado que ellos son solamente 10 para tanta teoría, y esta vez no es tan complicado lo que te piden: dada una lista de preguntas y sus respectivas respuestas, determinar si es posible saber con seguridad cuál es la solución.
Input
N líneas siguientes : cada una contiene dos secuencias de longitud exactamente 4. La primera será una pregunta y la segunda, su respuesta. La pregunta estará compuesta de dígitos del 1 al 6 (incluidos) y la respuesta estará compuesta de caracteres '1' (un toro), '0' (una vaca) o '-' (que no indica nada, usado solamente para completar la respuesta). En las respuestas se garantiza que siempre los '1' estarán antes que los '0' y los '-', y que los '0' estarán antes que los '-'. Siempre habrá al menos una solución posible.
Output
Sample test(s)
Hints
Hint
En el primer ejemplo, hay dos posibles soluciones: 1241 y 1242.