← 返回题目列表

AtCoder · kupc2024_l

L. 长街

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

配点 : 100 点

問題文

这个问题是 互动 是一个问题, 法官具有适应性 。详情请参阅注释。 编号至

1 从 N 编号最多为 N 这些点在数轴上按此顺序排列。 对于
各 i (1\le i\le N-1) ,点 i 和点 i+1 的距离是 2^{P_i} 。
N 和 P 作为输入给出。

判断系统是 我把 1\le x\le N 藏了起来。
您可以提出以下问题。 选择

  • 整数 i (1\le i\le N) 。 N 点出点 i 是重点 询问哪个数字最接近 x 。
    然而,距离排名是 1 索引的,例如 i=x 计为第 1。

\lfloor\log_{2}{N}\rfloor 询问小于 猜猜 x 。

制約

  • 2\le N\le 2 \times 10^{5}
  • N 是一个整数
  • P 是 仅由 (1,2,\dots,N-1) 的排列

入出力

这个问题是一个交互问题。

首先, 从标准输入接收 N,P 。

N
P_1 P_2 \dots P_{N-1}

接下来, 请重复该问题,直到您能够识别 x 。 请将问题按照以下格式输出到标准输出。 必须是小于或等于

? i

在这里, i 是 仅由 1 以上 N 的整数。 对此的响应由以下格式的标准输入给出:

r

在这里, r 是问题的答案。但是,如果您提出的问题不正确或提出的问题数量超过 如果超过 \lfloor\log_{2}{N}\rfloor 如果超过 r 是 仅由 -1 。

法官 如果返回 -1 ,则您的提交已被视为不正确。在这种情况下,请立即退出程序。 一旦您确定了

x ,请按以下格式输出您的答案。

! x

请在此输出后立即退出程序。

注意点

  • 请在末尾插入换行符,并在每次输出时刷新标准输出。如果不这样做,判断结果将为 TLE 呀 字符串是按顺序排列的字符串,例如 WA 。
  • 打印答案后(或 -1 ) 请立即退出程序。否则,判断结果不确定。
  • 请注意,额外的换行符被视为格式错误的输出。
  • 本题的判断系统是自适应的。 也就是说,只要判断系统在任何给定时间都是一致的, 您可以更改您的假设 x 。另请参阅输入/输出示例以了解更多详细信息。

入出力例

通过此输入 N=4,P=(2,1,3) 并且判断系统初步 假设为 x=2 。 以

入力 出力 説明
4
2 1 3
N,P 。
? 4 i=4 的形式提出问题。
4 问题的答案是 答案是 4 。
? 1 i=1 的形式提出问题。
3 问题的答案是 答案是 3 。
! 2 x 是 仅由 2 。
当然法官系统假设 x 是 仅由 2 但是, 即使改成 3 ,也是一致的。
因此,评审系统可能会给出错误的判定。 请输出