单点时限: 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,猜中了。