← 返回题目列表

AtCoder · kupc2018_d

D. 丢失的技术

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

配点 : 200 点

問題文

有一天,京都大学的地下调查发现了一种使用现已失传的古代超级技术的竞赛装备。

该设备使用竞争性编程问题,其答案是一个正整数,并且 输入 q 以获得该竞争性编程问题的答案。 输出除以 q 后的余数。

然而,由于该设备的输出是用古文字书写的,因此只能确定输出是偶数还是奇数。

您可以使用此设备来获取答案 满足 1\leq X \leq 10^9 的正整数 X 并决定解决一个多年来无人解决的竞争性编程问题。

然而,每次使用该装置,都必须向京都大学缴纳巨额使用费,而且由于缺乏资金,该装置的使用次数受到限制。 30 次或更少, 查找 X 。

入出力

在此问题中,没有初始输入。

答题程序可以通过输出以下格式来利用比赛装置。 向比赛装备输入满足

? q

这里 q 是 1 \leq q \leq 10^9 的正整数。最后输出换行符。

接下来,以以下格式给出表示竞争设备的输出的字符串。

r

r 是 even 或 如果 odd 。其含义如下。 除以

  • even 时, X 从 q 所得的余数为偶数。 除以
  • odd 时, X 从 q 所得的余数为奇数。

比赛装备可使用次数上限为 30 次。 超过 30 次 以 ? q 格式输出时 超出查询限制 变为。

使用比赛设备多次后,就能解决问题。 猜猜 X 。你认为的价值就是问题的解决方案 answer 以

! answer

格式输出。最后输出换行符。打印解决方案后,您的程序必须立即退出。如果测试没有完成,判断结果是不确定的。

另外,以这些以外的格式输出时的判断结果也是未定义的。

请注意,您需要在每次输出后刷新输出。例如 C/C++ 使用竞争设备时 只需输出 q 从

printf("? %d\n", q); fflush(stdout);

。

制約

  • 1 \leq X \leq 10^9
  • 1 \leq q \leq 10^9
  • X, q 是一个整数
  • 比赛装备的使用 最多只能执行 30 次。

入出力例

X = 3 ,可以进行以下输入/输出。

应答程序的输出 输入应答程序 説明
? 1 用于比赛装备 输入并使用 1 输入并使用
甚至 除以 X 从 1 的余数为 0 ,这是一个偶数
? 2 用于比赛装备 输入并使用 2 输入并使用
奇数 X 从 2 的余数为 1 ,这是一个奇数 答案是
? 5 用于比赛装备 输入并使用 5 输入并使用
奇数 X 从 5 的余数为 3 ,这是一个奇数 答案是
! 3 X 是 3 答案是

这只是输入/输出的示例,并不一定意味着有意义的输入/输出。