문제

이 문제는 인터랙티브 문제다. 인터랙티브 문제란 문제에 대한 답을 단순히 출력하는 것이 아니라, 채점기와 상호작용하여 정답을 알아내는 문제다.

채점기는 $1$부터 $10$ 사이의 무작위 정수를 하나 들고 있다. 이 수를 맞추는 프로그램을 작성해보자.

인터랙티브

당신의 프로그램은 최대 10번의 질문을 할 수 있다. 질문은 아래의 형식으로 출력한다.

• ? x : 채점기가 갖고 있는 수가 $x$인지 물어본다. ($1\le x\le 10$)

당신의 프로그램이 질문을 한 뒤에, 채점기는 자신이 갖고 있는 수가 $x$랑 같으면 YES를 출력해주고, 다르다면 NO를 출력해준다.

여러분은 C의 scanf나 C++의 cin, Python의 input 등의 표준 입력 방법을 통해 채점기의 출력을 입력으로써 받아올 수 있다.

질문을 한 뒤에는 반드시 출력 버퍼를 비워줘야 한다. 그렇지 않으면 예상치 못한 결과를 얻을 수 있다.

아래 방법으로 출력 버퍼를 비울 수 있다.

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

수가 무엇인지 알았다면 아래의 형식으로 답을 출력한다.

• ! x : 채점기가 갖고 있는 수는 $x$이다.

답을 출력한 후에는 반드시 프로그램을 종료해야 하며, 그 외의 경우에는 TLE 에러를 받을 수 있으니 주의하자!

 
NO

NO

YES

? 1

? 2

? 3

! 3

입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해, 의도적으로 줄 간격을 조절한 것이다. 실제 입출력과 다른 것에 유의하자.

힌트

다음 Python 소스코드로 이 문제를 해결할 수 있다.

for i in range(1, 10+1):
    print("?", i)
    if input() == "YES":
        print("!", i)
        break

그러나 만약 다음과 같은 Python 소스코드를 제출하면 시간 초과를 받을 것이다.

import sys
input = sys.stdin.readline

for i in range(1, 10+1):
    print("?", i)
    if input() == "YES":
        print("!", i)
        break