分数: 800 点
问题陈述
这是一项交互式任务。
Snuke 有一个最喜欢的正整数, N。你最多可以问他以下类型的问题 64 次:“是 n 你最喜欢的整数?”识别 N.
Snuke 是扭曲的,当被问到“是 n 你最喜欢的整数?”,如果满足以下两个条件之一,他回答“是”,否则回答“否”:
- 两者 n \leq N 和 str(n) \leq str(N) 按住。
- 两者 n > N 和 str(n) > str(N) 按住。
在这里, str(x) 是十进制表示形式 x (不带前导零)作为字符串。例如, str(123) = 123 和 str(2000) = 2000。
字符串按字典顺序进行比较。 11111 < 123 和 123456789 < 9.
约束
- 1 \leq N \leq 10^{9}
输入和输出
按照以下格式将您的问题写入标准输出:
? n
在这里, n 必须是介于 1 和 10^{18} (含)。
然后,应按以下格式从标准输入给出问题的答复:
ans
在这里, ans 是 Y or N. Y 代表“是”; N 代表“否”。
最后,按照以下格式写下您的答案:
! n
在这里, n=N 必须保留。
判断
- 每次输出后,您必须刷新标准输出。 否则你可能会得到
TLE. - 打印答案后,必须立即终止程序。否则,法官的行为是不确定的。
- 当你的输出无效或不正确时,判断的行为是未定义的(它不一定给出
WA).
示例
以下是该案例的示例通讯 N=123:
| 输入 | 输出 |
|---|---|
? 1 |
|
Y |
|
? 32 |
|
N |
|
? 1010 |
|
N |
|
? 999 |
|
Y |
|
! 123 |
- 自从 1 \leq 123 和 str(1) \leq str(123),第一个回答是“是”。
- 自从 32 \leq 123 但是 str(32) > str(123),第二个回答是“否”。
- 自从 1010 > 123 但是 str(1010) \leq str(123),第三个回答是“否”。
- 自从 999 \geq 123 和 str(999) > str(123),第四个响应是“是”。
- 程序成功识别 N=123 四题,从而通过此案。