分数: 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}。 因此,如果程序在这里立即退出,则该案例将被判断为正确解决。