← 返回题目列表

AtCoder · abc299_d

G. 通过查询查找

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

分数: 400 点

问题陈述

这是一个 交互式任务,您的程序和法官通过标准输入和输出进行交互。

判断有一串长度 N 组成 0 和 1: S = S_1S_2\ldots S_N。 在这里, S_1 = 0 和 S_N = 1.

给你长度 N of S,但不是内容 S。 相反,你最多可以问法官 20 问题如下。

  • 选择一个整数 i 这样 1 \leq i \leq N 并询问值 S_i.

打印一个整数 p 这样 1 \leq p \leq N-1 和 S_p \neq S_{p+1}.
可以证明这样 p 在这个问题的设置下始终存在。

约束

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

输入和输出

首先,接收长度 字符串的 N 来自标准输入的 S :

N

那你最多去问法官 20 问题如问题陈述中所述。

按以下格式将每个问题打印到标准输出,其中 i 是满足以下条件的整数 1 \leq i \leq N:

? i

对此,值 S_i 将从标准输入以以下格式给出:

S_i

在这里, S_i is 0 or 1.

当你找到一个整数时 p 满足问题陈述中的条件,按以下格式打印,并立即退出程序:

! p

如果存在多个解决方案,您可以打印其中任何一个。

注释

  • 在每条消息的末尾打印换行符并刷新标准输出。否则,您可能会得到一个 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 = 5 作为满足条件的整数。

对于所呈现的 p = 5,我们有 1 \leq p \leq N-1 和 S_p \neq S_{p+1}。 因此,如果程序在这里立即退出,则该案例将被判断为正确解决。