← 返回题目列表

AtCoder · arc078_c

E. 尴尬的反应

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

分数: 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 四题,从而通过此案。