D - Find by Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

この問題は インタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

ジャッジが 0 と 1 のみからなる長さ N の文字列 S = S_1S_2\ldots S_N を持っています。 文字列 S は、S_1 = 0 および S_N = 1 を満たします。

あなたには S の長さ N が与えられますが、S 自体は与えられません。 その代わり、あなたはジャッジに対して以下の質問を 20 回まで行うことができます。

  • 1 \leq i \leq N を満たす整数 i を選び、S_i の値を尋ねる。

1 \leq p \leq N-1 かつ S_p \neq S_{p+1} を満たす整数 p を 1 個出力してください。
なお、本問題の条件下でそのような整数 p が必ず存在することが示せます。

制約

  • 2 \leq N \leq 2 \times 10^5

入出力

最初に、文字列 S の長さ N を標準入力から受け取ってください。

N

次に、あなたはジャッジに対して問題文中の質問を 20 回まで繰り返すことができます。

質問は、以下の形式で標準出力に出力してください。 ここで、i は 1 \leq i \leq N を満たす整数でなければなりません。

? i

これに対する応答として、S_i の値が次の形式で標準入力から与えられます。

S_i

ここで、S_i は 0 または 1 です。

問題文中の条件を満たす整数 p を見つけたら、解答を以下の形式で出力してください。 その後、ただちにプログラムを終了してください。

! p

答えが複数ある場合、どれを出力しても正解とみなされます。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
  • 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
  • 文字列 S はあなたとジャッジの対話の開始時に固定され、あなたが行った質問などに応じて変更されることはありません。

入出力例

以下は、N = 7, S = 0010011 の場合の入出力例です。

入力 出力 説明
7 N が与えられます。
? 1 S_1 が何かをジャッジに質問します。
0 質問に対する答えとして S_1 = 0 がジャッジから返されます。
? 6 S_6 が何かをジャッジに質問します。
1 質問に対する答えとして S_6 = 1 がジャッジから返されます。
? 5 S_5 が何かをジャッジに質問します。
0 質問に対する答えとして S_5 = 0 がジャッジから返されます。
! 5 問題文中の条件を満たす整数 p として、p = 5 を解答します。

解答した p = 5 について、1 \leq p \leq N-1 かつ S_p \neq S_{p+1} が成り立ちます。 よって、この後ただちにプログラムを終了することで、正解と判定されます。

Score : 400 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 N consisting of 0 and 1: S = S_1S_2\ldots S_N. Here, S_1 = 0 and S_N = 1.

You are given the length N of S, but not the contents of S. Instead, you can ask the judge at most 20 questions as follows.

  • Choose an integer i such that 1 \leq i \leq N and ask the value of S_i.

Print an integer p such that 1 \leq p \leq N-1 and S_p \neq S_{p+1}.
It can be shown that such p always exists under the settings of this problem.

Constraints

  • 2 \leq N \leq 2 \times 10^5

Input and Output

First, receive the length N of the string S from Standard Input:

N

Then, you get to ask the judge at most 20 questions as described in the problem statement.

Print each question to Standard Output in the following format, where i is an integer satisfying 1 \leq i \leq N:

? i

In response to this, the value of S_i will be given from Standard Input in the following format:

S_i

Here, S_i is 0 or 1.

When you find an integer p 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 S 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, N = 7 and S = 0010011.

Input Output Description
7 N is given.
? 1 Ask the value of S_1.
0 The judge responds with S_1 = 0.
? 6 Ask the value of S_6.
1 The judge responds with S_6 = 1.
? 5 Ask the value of S_5.
0 The judge responds with S_5 = 0.
! 5 Present p = 5 as an integer satisfying the condition.

For the presented p = 5, we have 1 \leq p \leq N-1 and S_p \neq S_{p+1}. Thus, if the program immediately quits here, this case will be judged as correctly solved.