27865번 - 랜덤 게임? 인터랙티브

이 문제는 인터랙티브 문제이다.

처음에 인터랙터는 $1$부터 $N$까지 정수 중에서 균등한 확률로 수를 하나를 뽑는다. 질문을 통해 인터랙터가 현재 가지고 있는 수를 맞추면 이 문제를 맞힐 수 있다.

당신은 다음과 같은 질문을 최대 $20\,000$번 할 수 있다.

• 현재 가지고 있는 수가 $x$인가? $(1\le x\le N)$

만약 질문의 답이 '아니오.'라면 인터랙터는 현재 가지고 있는 수를 버리고 새로 수를 뽑는다.

양의 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$

다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, 인터랙터가 가지고 있는 수가 무엇인지 질문할 수 있다.

• ? x : 현재 인터랙터가 가지고 있는 수가 $x$인지 확인한다. $(1\le x\le N)$

질문을 한 뒤, 당신은 인터랙터에게서 문자 하나를 입력받아서 질문의 답을 알 수 있다.

• Y : 현재 인터랙터가 가지고 있는 수는 $x$와 같다.
• N : 현재 인터랙터가 가지고 있는 수는 $x$와 다르다. 이후 인터랙터는 현재 가지고 있는 수를 버리고 새로 수를 뽑는다. 수를 뽑을 때는 질문의 답을 참고하지 않고 $1$부터 $N$까지 정수 중에서 균등한 확률로 수를 하나를 뽑는다.

질문을 한 후에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다. 그렇지 않으면, 시간 초과 또는 런타임 에러를 받는다. 범위를 벗어난 $x$값을 질문하거나 잘못된 형식으로 질문하면 틀렸습니다를 받는다. 또한 $20\,000$회 넘게 질문을 하면 틀렸습니다를 받는다.

만약 인터랙터가 현재 가지고 있는 수를 알아낸 경우, 표준 출력 스트림으로 다음 한 줄을 출력한다.

• ! y : 현재 인터랙터가 가지고 있는 수는 $y$이다.

답을 출력한 이후에는 표준 출력 버퍼를 비우고 프로그램을 바로 종료하여야 한다. 그렇지 않으면 예상하지 못한 채점 결과를 받을 수 있다.

각 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()