시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 1024 MB605573912.829%

문제

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

'코드포스'는 유저의 레이팅에 따라 닉네임의 색깔을 바꿔준다. ko_osaga님을 제외한 Orange Cup의 운영진과 검수진들은 전부 2100 이상 2399 이하의 코드포스 레이팅을 가지고 있어서 오렌지색 닉네임을 갖는다. ko_osaga의 코드포스 레이팅은 3000이 넘지만, 실력은 오렌지이기 때문에 이 대회의 검수진으로 참여할 수 있었다.

ko_osaga의 실력은 가상의 코드포스 계정인 ko_orange의 레이팅 $x$이다. 당신은 다음과 같은 질문을 최대 $q$번 할 수 있다.

  • ko_orange의 레이팅은 $y$ 이상인가요? ($2100 \leq y \leq 2399$)

ko_orange는 대부분의 경우 정확한 답변을 하지만 최대 1번 ko_osaga의 레이팅과 헷갈려서 레이팅이 $y$ 미만이더라도 이상이라고 대답한다. 이 질문을 이용해 당신은 $x$를 구해야 한다. 단, 질문의 개수를 최소화할 필요는 없으며, 모든 레이팅은 정수이다.

입력

당신은 한 번의 프로그램 실행에서 $T$개의 테스트 데이터를 처리하여야 한다. 입력의 첫 줄에는 테스트 데이터의 수 $T$가 주어진다.

출력

각 테스트 데이터에 대해 아래와 같은 과정으로 채점 프로그램과의 소통이 진행된다.

당신은 하나의 테스트 데이터에서 총 $q$번, ko_orange의 레이팅이 정수 $y$ 이상인지를 질문할 수 있다. 이때 $2100 \le y \le 2399$를 만족해야 한다. 질문은 "$? \ y$"과 줄 바꿈을 (따옴표 없이) 출력하는 것으로 이루어진다. 질문을 한 뒤, 당신은 정수 하나를 입력받아서 질문의 답을 알 수 있다. 이 답이 1인 경우 ko_orange의 레이팅이 $y$ 이상이라는 것이고, 답이 0인 경우 $y$ 미만이라는 것이다.

만약 ko_orange의 레이팅을 알아냈다면, "$! \ x$"와 줄 바꿈을 출력한다. $x$는 ko_orange의 실제 레이팅과 같은 값이어야 한다.

모든 출력 뒤에 출력 버퍼를 비우지 않거나, 올바르지 않은 답을 출력하거나, 출력 형식을 어길 경우 예상하지 못한 채점 결과를 받을 수 있다.

제한

  • $1 \le T \le 300$
  • $2100 \leq x \leq 2399$
  • $2100 \leq y \leq 2399$
  • $x$, $y$는 정수이다.

서브태스크

번호 배점 제한
1 23

$q = 18$

2 29

$q = 14$

3 48

$q = 13$

예제 입력 1

2

1

0
​

0
​

예제 출력 1

​
​? 2200

? 2200

! 2150
? 2101

! 2100

빈 줄은 참가자의 이해를 돕기 위함으로, 실제 입력과 출력에서는 나타나지 않는다.

노트

당신의 출력을 즉각적으로 채점 프로그램에 전달하기 위해, 당신은 모든 출력 뒤에 출력 버퍼를 비워야 한다. 언어별로 출력 버퍼를 비우는 방법은 아래와 같다.

  • C: fflush(stdout);
  • C++: std::cout.flush();
  • Java: System.out.flush();
  • Python: stdout.flush()
  • 기타 언어의 경우 각 언어의 documentation을 참조하라.

출처

Contest > Orange Cup > Orange Cup C번

채점 및 기타 정보

  • 예제는 채점하지 않는다.