atcoder#ABC299D. [ABC299D] Find by Query
[ABC299D] Find by Query
Score : points
Problem Statement
This is an interactive task, where your program and the judge interact via Standard Input and Output.
The judge has a string of length consisting of and : . Here, and .
You are given the length of , but not the contents of . Instead, you can ask the judge at most questions as follows.
- Choose an integer such that and ask the value of .
Print an integer such that and . It can be shown that such always exists under the settings of this problem.
Constraints
Input and Output
First, receive the length of the string from Standard Input:
N
Then, you get to ask the judge at most questions as described in the problem statement.
Print each question to Standard Output in the following format, where is an integer satisfying :
? i
In response to this, the value of will be given from Standard Input in the following format:
S_i
Here, is or .
When you find an integer satisfying the condition in the problem statement, print it in the following format, and immediately quit the program:
! p
If multiple solutions exist, you may print any of them.
Notes
- Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
- If there is malformed output during the interaction or your program quits prematurely, the verdict will be indeterminate.
- After printing the answer, immediately quit the program. Otherwise, the verdict will be indeterminate.
- The string will be fixed at the start of the interaction and will not be changed according to your questions or other factors.
Sample Input and Output
In the following interaction, and .
Input | Output | Description |
---|---|---|
7 |
is given. | |
? 1 |
Ask the value of . | |
0 |
The judge responds with . | |
? 6 |
Ask the value of . | |
1 |
The judge responds with . | |
? 5 |
Ask the value of . | |
0 |
The judge responds with . | |
! 5 |
Present as an integer satisfying the condition. | |
For the presented , we have and . Thus, if the program immediately quits here, this case will be judged as correctly solved.