The Good, the Bad and the Ugly
시간 제한2초메모리 제한512 MB
수직선 위에서 움직이는 세 종류의 플레이어를 판별한다. 매 라운드 + 또는 -를 외치고 위치가 0인지만 들으며 30m 라운드 안에 정체를 밝힌다.
문제
This problem was supposed to have a nice long legend about the Wild Wild West, but the author did not manage to write it in time, so use the power of your imagination!
Consider a number line. A player initially stands at the position . At the beginning of each round, you can say either "+" or "-". After that, the player changes position according to what you said. More precisely, if you say and the player stood at position , then he moves to position , where and are two integer constants.
You do not know the exact values , and , but you know that the player is either the Good, the Bad or the Ugly (yeah, imagination!):
- The Good player has , , ;
- The Bad player has , , ;
- The Ugly player has either or and either and or and .
As you can see, the starting position of the player depends on some integer constant ()... unfortunately, you do not know it too.
After each round, the player tells you if he now stands at or not.
It appears that, by playing several rounds, you can uniquely determine if the player is Good, Bad or Ugly. Do it in no more than rounds.
In each test, the values , , and are chosen according to the above rules. They are fixed in advance and don't change during the checking process.