The Good, the Bad and the Ugly

시간 제한2초메모리 제한512 MB

요약
수직선 위에서 움직이는 세 종류의 플레이어를 판별한다. 매 라운드 + 또는 -를 외치고 위치가 0인지만 들으며 30m 라운드 안에 정체를 밝힌다.
난이도

어려움10점 중 9점

유형
수학, 정수론, 이분 탐색, 시뮬레이션
정답자
아직 제출이 없습니다

문제

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 x=px = p. 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 tt and the player stood at position xx, then he moves to position x′=x+d_tx' = x + d\_t, where d_+d\_+ and d_−d\_- are two integer constants.

You do not know the exact values pp, d_0d\_0 and d_1d\_1, but you know that the player is either the Good, the Bad or the Ugly (yeah, imagination!):

  • The Good player has p=mp = m, d_+=2d\_+ = 2, d_−=−1d\_- = -1;
  • The Bad player has p=−mp = -m, d_+=1d\_+ = 1, d_−=−2d\_- = -2;
  • The Ugly player has either p=mp = m or p=−mp = -m and either d_+=1d\_+ = 1 and d_−=−1d\_- = -1 or d_+=−1d\_+ = -1 and d_−=1d\_- = 1.

As you can see, the starting position of the player depends on some integer constant mm (1≤m≤10001 \le m \le 1000)... unfortunately, you do not know it too.

After each round, the player tells you if he now stands at x=0x = 0 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 30m30 m rounds.

In each test, the values mm, pp, d_+d\_+ and d_−d\_- are chosen according to the above rules. They are fixed in advance and don't change during the checking process.

예제1

  1. 예제 1

    입력
    
    0
    
    1
    
    예상 출력
    -
    
    -
    
    ! good