3646. 猜价格

单点时限: 1.0 sec

内存限制: 512 MB

你女朋友最近叒不理你了。这一定是因为你双十一没有给她买东西。异地恋实在是太辛苦了,浦西到浦东的距离,对于你来说,就像是上海到多伦多的距离。

曾有诗这样写道:

世上最遥远的距离,不是生与死的距离,不是天各一方,而是我就站在你面前,你却不知道我爱你。

因此你决定参加某猜价格小游戏,猜对了就可以获得送女朋友的礼物了。但是这个游戏比普通的猜价格更加困难一些,因为可能会传递给你错误信息。

给定一个 $1$ 到 $2^n-1$ 之间的价格。你要把它猜出来。

每次只会回答是 >, < 还是 =,分别表示你猜的价格是太大了,还是太小了,还是猜中了。

另外,在任意连续 $k$ 次回答中,会有恰好一次是「反话」。他会把 > 说成 <,把 < 说成 >。但是 = 还是 =

你只有 $2n$ 次机会(包括猜中的那一次)。

交互流程

首先会输入两个整数 $n$ 和 $k$ ($1 \le n \le 60$, $1 \le k \le 10^9$)。

每一次,你都要猜一个 $1$ 到 $2^n-1$ 之间的数。然后 oxx 会回答你 >, < 或者 =。如果回答是 =,你的程序应该立即退出。

如果你使用了超过 $2n$ 次机会,你会得到 Wrong answer;如果你输出了不合法的内容,会得到 Runtime errorWrong answer;运行时间超限会导致 Time limit exceeded 或者 Idleness limit exceeded

注意,在每次输出后要清空缓冲区。

样例

Input
2 4
1

3

2
Output
<

<

=

提示

样例中猜测的范围是 $[1,3]$。连续 4 次中必有 1 次是假的。

第一次猜 1,偏小,回答 <

第二次猜 3,偏大,但是假了,回答 <

第三次猜 2,猜中了。

46 人解决,104 人已尝试。

56 份提交通过,共有 975 份提交。

5.9 EMB 奖励。

创建: 6 年前.

修改: 6 年前.

最后提交: 1 年,11 月前.

来源: EOJ Monthly 2018.11

题目标签