#347 보물찾기

Statement

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

$100 \times 100$ 격자 위에 보물상자 $10$ 개가 숨겨져 있다.

격자의 행 번호와 열 번호는 모두 $1$ 이상 $100$ 이하의 정수이다. 격자의 한 칸은 두 정수 $(x,y)$ 로 나타내며, 이는 $x$ 행 $y$ 열의 칸을 의미한다.

당신은 인터랙터와 상호작용하며 보물상자의 위치를 모두 찾아야 한다. 모든 보물 상자의 위치는 서로 다르다.

사용할 수 있는 쿼리는 다음 두 종류이다.

두 칸 $(x_1,y_1)$ 과 $(x_2,y_2)$ 사이의 맨해튼 거리는 $|x_1-x_2|+|y_1-y_2|$ 이다.

보물상자 $10$ 개의 위치를 모두 정확히 찾아내는 프로그램을 작성하여라.

프로그램 시작 시 참가자 프로그램에 주어지는 입력은 없다. 따라서 바로 쿼리를 시작하면 된다.

참가자 프로그램은 표준 출력으로 쿼리를 출력하고, 표준 입력으로 인터랙터의 응답을 읽어야 한다.

? 쿼리는 다음 형식으로 출력한다.

? x y

이때 $1 \le x,y \le 100$ 이어야 한다. 이 쿼리에 대해 인터랙터는 현재 남아 있는 보물상자 중 $(x,y)$ 와의 맨해튼 거리의 최솟값을 정수 하나로 반환한다.

! 쿼리는 다음 형식으로 출력한다.

! x y

이때 $1 \le x,y \le 100$ 이어야 한다. 현재 $(x,y)$ 에 보물상자가 있으면 인터랙터는 1을 반환하고, 해당 보물상자는 사라진다. 현재 $(x,y)$ 에 보물상자가 없으면 오답 처리된다.

! 쿼리를 정확히 $10$ 번 성공하면 참가자 프로그램은 즉시 종료해야 한다.

각 쿼리를 출력한 뒤에는 반드시 출력 버퍼를 비워야 한다.

인터랙터는 적응적이다.

? 쿼리를 사용한 횟수를 $Q$ 라고 하자. 점수 $S$ 는 다음과 같이 정해진다.

S= \begin{cases} 100 & (Q \le 100)\\ \left\lfloor 100 \cdot 0.05^{\left(\frac{\log(Q/100)}{\log 100}\right)^2} \right\rfloor & (100 < Q \le 10000)\\ 0 & (Q>10000) \end{cases}

단, 보물상자 $10$ 개의 위치를 모두 정확히 보고하지 못하거나 잘못된 쿼리를 사용하면 점수는 $0$ 점이다.

쿼리 수에 따른 점수 분포는 다음과 같다.

Input

Output

이 예시는 쿼리의 동작을 설명하기 위한 것이다. 실제 문제와 달리, 보물상자가 $(37,42)$ 에 하나만 있다고 가정한다.

참가자 프로그램이 ? 1 1을 출력하면 인터랙터는 $|37-1|+|42-1|=77$ 을 반환한다.

참가자 프로그램이 ? 37 1을 출력하면 인터랙터는 $|37-37|+|42-1|=41$ 을 반환한다.

참가자 프로그램이 ? 37 42를 출력하면 인터랙터는 $0$ 을 반환한다.

참가자 프로그램이 ! 37 42를 출력하면 보고가 맞으므로 인터랙터는 $1$ 을 반환하고, 해당 보물상자는 사라진다.

실제 채점에서는 보물상자가 $10$ 개 있으며, ! 쿼리를 정확히 $10$ 번 성공해야 한다.