配点: 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 提供后,如果程序没有立即结束,评分结果将不定义。
- 每次输出时请刷新标准输出。否则,
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 |