#BT08. 会翻面的比较器

会翻面的比较器

题目描述

这是一道交互题。评测器固定一个隐藏整数 h∈[1,n]h\in[1,n],以及一个隐藏开关 b∈{0,1}b\in\{0,1\}。 你可以询问整数 x∈[0,n]x\in[0,n],得到

[h≤x]xor⁡b.[h\le x]\mathbin{\operatorname{xor}}b.

其中 [P][P] 在命题 PP 成立时为 11,否则为 00。整个测试中 h,bh,b 保持不变。 请确定 hh。

交互协议

程序开始时读取两个整数 n Q,其中 Q=1+⌈log⁡2n⌉Q=1+\lceil\log_2 n\rceil 为最多询问次数。 输出 ? x 并换行刷新,然后读取一个整数 0 或 1。 确定答案后输出 ! h 并换行刷新,程序结束。最终答案不占询问次数。 评测器会把非法指令、越界询问、超过次数或错误答案判为错误并结束交互。 本题使用标准输入输出交互,提交完整程序。

数据范围

1≤n≤1091\le n\le10^9,1≤h≤n1\le h\le n,b∈{0,1}b\in\{0,1\}。

样例交互 1

该演示取 n=8,h=5,b=1n=8,h=5,b=1。评测器首先发送 8 4。

选手输出 评测器回复
? 0 1
? 4
? 6 0
? 5
! 5 交互结束

样例交互 2

该演示取 n=1,h=1,b=0n=1,h=1,b=0。评测器首先发送 1 1,选手可以直接输出 ! 1 结束。

本地运行

附件local_judge.py可运行任意已编译的选手程序: python local_judge.py 8 5 1 ./solution。