单点时限: 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 error
或 Wrong answer
;运行时间超限会导致 Time limit exceeded
或者 Idleness limit exceeded
。
注意,在每次输出后要清空缓冲区。
2 4 1 3 2
< < =
样例中猜测的范围是 $[1,3]$。连续 4 次中必有 1 次是假的。
第一次猜 1,偏小,回答 <
。
第二次猜 3,偏大,但是假了,回答 <
。
第三次猜 2,猜中了。