← 返回题目列表

AtCoder · typical90_ba

053. 离散探矿(★7)

中文机器翻译题面 查看原题

配点: 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