문제

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

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

인터랙티브

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

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

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

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

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

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

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

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

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

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

 
+

-

=

? 1

? 4

? 3

! 3

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

 
+

-

? 1

? 3

! 2