Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 7 点
問題文
これはインタラクティブな問題です。
T 個のテストケースに対して、以下の問題を解いてください。
長さ N の非負整数列 A = (A_1, A_2, \cdots, A_N) と整数 k (1 \le k \le N) が隠されている。数列 A は以下の条件を満たすことが分かっている。
- 1 \le i \le k-1 のとき A_i \lt A_{i+1}
- k \le i \le N-1 のとき A_i \gt A_{i+1}
整数 N が与えられた後、あなたはクエリを何回か送ることができる。 1 回のクエリでは、 1 \le i \le N なる i を 1 つ指定して A_i の値を得ることができる。できるだけ少ない回数のクエリで数列 A の最大値を求めよ。(詳しくは小課題・得点の項を参照)
制約
- 1 \leq T \leq 50
- 1 \leq N \leq 1500
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
小課題・得点
この問題に正解した場合の得点は、以下のように計算されます。
各テストケースに対するクエリの数の最大値を Q_{\mathrm{max}} とします。
- 1500 \lt Q_{\mathrm{max}} のとき 0 点
- 40 \lt Q_{\mathrm{max}} \leq 1500 のとき 1 点
- 22 \lt Q_{\mathrm{max}} \leq 40 のとき 3 点
- 15 \lt Q_{\mathrm{max}} \leq 22 のとき 4 点
- Q_{\mathrm{max}} \leq 15 のとき 7 点
入出力
最初に、テストケースの数 T が与えられます。
T
以降、 T 個のテストケースが続きます。
テストケースの最初では、次の形式で入力が与えられます。
N
クエリを送るには、以下の形式で出力してください。
? i
このクエリに対して、次の形式で返答が与えられます。
A_i
数列 A の最大値を答えるときは、その値を A_{\mathrm{max}} として次の形式で出力してください。
! A_{\mathrm{max}}
その後、次のテストケースがあれば続けて処理し、なければすぐにプログラムを終了してください。
プログラムが正しくないクエリを出力した場合は、 -1 が入力に与えられます。この場合はすぐにプログラムを終了してください。
注意
- この問題のジャッジはアダプティブです。つまり、これまでのクエリの内容に矛盾しない限り、数列の内容が変更される場合があります。
- すべてのテストケースで答えを出力した後、または -1 が与えられた後、プログラムをすぐに終了しなかった場合、採点結果は定義されません。
- 出力のたびに標準出力を flush してください。そうしない場合、
TLE
の可能性があります。 - AtCoder の仕様上、1 点以上を取れば
AC
と表示されることにご注意ください。(AC
でも満点ではない場合があります)
入出力例1
入力 | 出力 | 説明 |
---|---|---|
1 | T=1 | |
8 | 1 つ目のテストケースについて、 N=8 | |
? 6 | ||
6 | A_6=6 | |
? 7 | ||
9 | A_7=9 | |
? 8 | ||
1 | A_8=1 | |
! 9 |
数列 A は (1, 2, 3, 4, 5, 6, 9, 1) で、 k = 7 です。数列 A の最大値は 9 です。
例えば、 1 回目のクエリ終了時点では (7, 8, 9, 8, 7, 6, 5, 4) を数列 A としてもクエリの内容に矛盾しないので、この数列に変更される可能性があります。
入出力例2
入力 | 出力 | 説明 |
---|---|---|
2 | T=2 | |
1 | 1 つ目のテストケースについて、 N=1 | |
? 1 | ||
0 | A_1=0 | |
! 0 | ||
1 | 2 つ目のテストケースについて、 N=1 | |
? 1 | ||
1000000000 | A_1=1000000000 | |
! 1000000000 |