PROG0115 - The two towers
A king is angry at two scientists, so he decrees the following punishment. The scientists will be imprisoned in towers at opposite ends of the kingdom. Each morning, a guard at each tower will flip a coin and show the result to his prisoner. Each prisoner must then guess the result of the coin flip at the other tower. If at least one of the two guesses is correct, they will live another day. But as soon as both guesses are incorrect, they will be executed.
On the way out of the throne room, the scientists manage to confer briefly, and they come up with a plan that will spare them indefinitely. What strategy guarantees them to escape their execution forever?
There exists a rock-solid strategy that will lead to exactly one prisoner guessing correctly at all times. It's easiest to explain this strategy by observing that either both flips give the same or a different result. That is the paradigm shift you have to make to understand that the strategy simply is to decide which of the two prisoners will answer with the same result as the coin flip at his own tower and which prisoner will answer with the opposite result of the coin flip at his own tower. It might seem unlikely, but the following figure shows that this strategy guarantees that at least one guess will always be correct.
Input
The first two lines of input contain the outcomes of the coin flips at the towers of the first and second prisoner: head or tail. The third line indicates which scientist (first or second) will always say the same result as the one of the coin flip at his own tower. The other scientist will always answer with the opposite of the coin flip at his own tower.
Output
There are two lines of output that respectively contain the answer (head or tail) of the first and the second prisoner, if they follow the infallible strategy described above.
Example
Input:
head tail second
Output:
tail tail
Een koning is woest op twee wetenschappers uit zijn hofhouding en laat hen veroordelen tot de volgende straf. De wetenschappers zullen opgesloten worden in torens die zich aan twee uithoeken van het koninkrijk bevinden. Iedere ochtend zal de bewaker van elke toren een muntstuk opwerpen, en het resultaat daarvan aan de wetenschapper tonen die in de toren opgesloten zit. Elke gevange moet dan raden wat het resultaat is van de worp bij de andere toren. Indien minstens één van de twee gevangenen het juiste antwoord geeft, dan mogen ze alletwee nog een dag langer leven. Als ze echter beide het verkeerde antwoord geven, dan worden ze onmiddellijk geëxecuteerd.
Na het aanhoren van hun strafmaat, kunnen beide wetenschappers bij het verlaten van de troonzaal nog snel met elkaar overleggen. Welke strategie kunnen ze met elkaar afspreken om voor altijd aan hun executie te ontsnappen?
Er bestaat een onfeilbare strategie die garandeert dat er altijd juist één gevangene het juiste antwoord geeft. De makkelijkste manier om deze strategie uit te leggen is door vast te stellen dat de twee worpen ofwel hetzelfde resultaat opleveren of een verschillend resultaat opleveren. Als je dat eenmaal doorhebt, dan bestaat de strategie erin te beslissen wie van beide gevangenen hetzelfde resultaat zal zeggen als dat van zijn eigen worp en wie het tegenovergestelde resultaat zal zeggen als dat van zijn eigen worp. Het lijkt misschien onwaarschijnlijk, maar uit onderstaande afbeelding blijkt dat deze strategie er altijd toe zal leiden dat juist één van de twee personen het juiste antwoord zal geven, wat hen dus nog een dag extra laat leven.
Invoer
De eerste twee regels bevatten telkens het resultaat van de worp bij de toren van de eerste en de tweede gevangene: kop of munt. De derde regel geeft aan (eerste of tweede) welke van de twee gevangen hetzelfde zal zeggen als het resultaat van de worp bij zijn eigen toren. De andere persoon zal het tegenovergestelde zeggen.
Uitvoer
De uitvoer bestaat uit twee regels, die het antwoord bevatten (kop of munt) van respectievelijk de eerste en de tweede gevangene, als ze de onfeilbare strategie toepassen zoals hierboven omschreven.
Voorbeeld
Invoer:
kop munt tweede
Uitvoer:
munt munt
| Added by: | Peter Dawyndt |
| Date: | 2011-08-06 |
| Time limit: | 10s-30s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS