| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 419 | 106 | 77 | 25.413% |
이 문제는 인터랙티브 문제입니다.
흐즈로는 음이 아닌 정수 $x$ (0ドル \le x \le 10^{18}$)를 하나 가지고 정수 맞히기 게임을 하고자 합니다. 여러분은 질문을 하여 숨겨진 정수 $x$를 맞혀야 합니다. 하지만, 흐즈로는 지금까지 이러한 종류의 문제만 몇백 개 정도 있었다는 사실을 알고 있습니다. 그렇기에 흐즈로는 여러분이 문제를 쉽게는 풀 수 없도록 그 누구도 생각하지 못했을 종류의 질문을 생각해 냈습니다. 여러분이 사용할 수 있는 질문은 다음과 같습니다.
여러분은 두 음이 아닌 정수 $a$와 $b$를 정해서, 흐즈로에게 질문을 할 수 있습니다. 질문으로 주어진 두 정수 $a$와 $b$에 따라, 흐즈로는 다음 값을 계산합니다.
$$\sqrt{(x-a)}-b$$
흐즈로는 계산 결과에 따라 이 값이 양수인지, 음수인지, 아니면 0ドル$인지 여러분에게 알려줍니다. 75ドル$개 이하의 질문을 사용하여 정수를 맞힐 수 있다면 여러분이 승리하고, 질문의 개수가 75ドル$개를 초과할 경우 여러분이 패배합니다. 그러나, $x-a$가 음수가 되는 질문을 한다면 게임이 즉시 종료되고 여러분이 패배합니다. 여러분은 과연 정수의 값을 맞히고 흐즈로를 이길 수 있을까요?
첫 번째 줄에 테스트 케이스의 개수 $n$이 주어집니다. (1ドル \le n \le 100$)
여러분은 다음을 표준 출력 (stdout)으로 출력하여 질문을 할 수 있습니다.
? a b: $\sqrt{(x-a)}-b$의 값에 대해 질문합니다. (0ドル \le a,b \le 10^{18}$)인터랙터는 계산한 값에 따라 문자를 한 줄에 표준 입력 (stdin)으로 반환하는데, 값이 양수일 경우 +를, 음수일 경우 -를, 0ドル$일 경우 0을 반환합니다. 단, 질문의 개수가 75ドル$개를 초과하였거나 $x-a$의 값이 음수였을 경우 인터랙터는 결과로 !를 반환합니다. 그 즉시 프로그램을 정상 종료해야 하며, 이 경우 채점 결과로 틀렸습니다를 받습니다. 프로그램이 정상 종료되지 않으면 그 외의 채점 결과를 받을 수 있음에 유의하세요.
만약 $x$의 값을 알아낸 경우, 표준 출력 스트림으로 다음을 한 줄에 출력해야 합니다.
! v: $x$의 값은 $v$입니다. (0ドル \le v \le 10^{18}$)그 후 해결해야 할 테스트 케이스가 남아 있다면 다음 테스트 케이스로 넘어가고, 그렇지 않다면 즉시 프로그램을 종료해야 합니다. ! v를 출력하는 것은 질문의 개수에 포함되지 않습니다.
모든 테스트 케이스에 대해서 $x$의 값을 알아내는 데 성공하였다면 채점 결과로 맞았습니다를 받습니다. 그렇지 않다면 틀렸습니다를 받습니다.
각 줄을 출력한 후에는 표준 출력 버퍼를 flush해 주어야 합니다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같습니다.
fflush(stdout)cout.flush()System.out.flush()sys.stdout.flush()본 문제의 인터랙터는 적응적이지 않습니다. 다시 말해, 모든 테스트 케이스에서 $x$의 값은 인터랙션 이전부터 고정되어 있으며 인터랙션 도중에 변하지 않습니다.
2 + - 0 + 0
? 0 0 ? 1 1 ? 1 0 ! 1 ? 0 0 ? 1 1 ! 2
예제의 줄과 줄 사이의 공백은 인터랙션의 순서를 표현하기 위해 임의로 추가되었으며, 실제 입출력에는 줄과 줄 사이에 공백이 없음에 유의해야 합니다.
예제의 첫 번째 테스트 케이스에서 숨겨진 정수는 1ドル$입니다. 예제 출력의 질문과 그에 대응되는 답은 다음과 같습니다.
+를 반환합니다.-를 반환합니다.0을 반환합니다.이 시점에서 $x=1$임을 알 수 있으므로, ! 1을 출력해 $x$의 값을 확정합니다.
예제의 두 번째 테스트 케이스에서 숨겨진 정수는 2ドル$입니다. 예제 출력의 질문과 그에 대응되는 답은 다음과 같습니다.
+를 반환합니다.0을 반환합니다.이 시점에서 $x=2$임을 알 수 있으므로, ! 2를 출력해 $x$의 값을 확정합니다.
본 문제는 입출력의 양이 많은 관계로 최악의 경우 입출력에 약 500ms 가량의 시간이 소요될 수 있습니다. 이 점에 유의하여 문제를 해결해 주시기 바랍니다.