这是一个交互问题。
娜塔莎要去火星。最后,娜塔莎坐上了火箭。她飞啊飞……但她感到无聊。她希望已经到达火星了!于是她决定给自己找点事做。她想不出还有什么比计算到这颗红色星球的距离更好的事情了。
让我们将 $$$x$$$ 定义为到火星的距离。不幸的是,娜塔莎不知道$$$x$$$。但已知 $$$1 \le x \le m$$$,其中 Natasha 知道数字 $$$m$$$。此外,$$$x$$$和$$$m$$$都是正整数。
娜塔莎可以问火箭问题。每个问题都是一个整数 $$$y$$$ ($$$1 \le y \le m$$$)。如果$$$x<y$$$,则问题的正确答案为$$$-1$$$;如果$$$x=y$$$,则$$$0$$$;如果$$$x>y$$$,则$$$1$$$。但火箭坏了——它并不总是能正确回答。准确地说:让当前问题的正确答案等于$$$t$$$,那么,如果火箭正确回答了这道问题,那么它会回答$$$t$$$,否则它会回答$$$-t$$$。
此外,火箭有一个长度为$$$n$$$的序列$$$p$$$。序列中的每个元素都是 $$$0$$$ 或 $$$1$$$。火箭按循环顺序处理该序列,即 $$$1$$$-st 元素、$$$2$$$-nd、$$$3$$$-rd、$$$\ldots$$$、$$$(n-1)$$$-th、$$$n$$$-th、$$$1$$$-st、$$$2$$$-nd、$$$3$$$-rd、 $$$\ldots$$$、$$$(n-1)$$$ 个、$$$n$$$ 个、$$$\ldots$$$。如果当前元素是 $$$1$$$,则火箭回答正确,如果 $$$0$$$ — 撒谎。娜塔莎不知道序列$$$p$$$,但她知道它的长度——$$$n$$$。
您可以向火箭提出不超过 $$$60$$$ 的问题。
帮助娜塔莎找到到火星的距离。假设娜塔莎提问时,到火星的距离没有改变。
如果您的解决方案没有从火箭收到 $$$0$$$ 答案,则该解决方案将不会被接受(即使到火星的距离是由已收到的火箭答案唯一确定的)。
输入
第一行包含两个整数 $$$m$$$ 和 $$$n$$$ ($$$1 \le m \le 10^9$$$, $$$1 \le n \le 30$$$) - 到火星的最大距离和序列 $$$p$$$ 中的元素数量。
互动
您可以向火箭提出不超过 $$$60$$$ 的问题。
要提出问题,请打印数字 $$$y$$$ ($$$1\le y\le m$$$) 和行尾字符,然后执行刷新操作并读取问题的答案。
如果程序读取 $$$0$$$,则距离正确,您必须立即终止程序(例如,通过调用 exit(0))。如果您忽略这一点,您可以获得任何结论,因为您的程序将继续从关闭的输入流中读取。
如果您的程序在某个时刻读取 $$$-2$$$ 作为答案,则它必须立即结束(例如,通过调用 exit(0))。您将收到“错误答案”的判决,这意味着请求不正确或请求数量超过 $$$60$$$。如果您忽略这一点,您可以获得任何结论,因为您的程序将继续从关闭的输入流中读取。
如果您的程序的请求不是 $$$-2^{31}$$$ 和 $$$2^{31}-1$$$(含)之间且不带前导零的有效整数,那么您可以获得任何结论。
如果您不打印任何内容或者忘记刷新输出,您可能会收到“超出空闲限制”的信息。
要刷新输出缓冲区,您可以使用(在打印查询和行尾之后):
- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。
黑客攻击
使用以下格式进行黑客攻击:
在第一行中,打印 $$$3$$$ 整数 $$$m,n,x$$$ ($$$1\le x\le m\le 10^9$$$, $$$1\le n\le 30$$$) — 到火星的最大距离,序列 $$$p$$$ 中元素的数量以及到火星的当前距离。
在第二行中,输入 $$$n$$$ 数字,每个数字等于 $$$0$$$ 或 $$$1$$$ — 序列 $$$p$$$。
被黑客攻击的解决方案将无法访问数字 $$$x$$$ 和序列 $$$p$$$。
示例
输入 #1
5 2 1 -1 -1 1 0
输出 #1
1 2 4 5 3
注意
在示例中,黑客攻击将如下所示:
5 2 3
1 0
这意味着当前到火星的距离等于$$$3$$$,娜塔莎知道不超过$$$5$$$,火箭按顺序回答:正确、错误、正确、错误……
真的:
第一个查询($$$1$$$)的正确答案是$$$1$$$,火箭正确答案是:$$$1$$$;
对第二个查询($$$2$$$)正确答案是$$$1$$$,火箭错误回答:$$$-1$$$;
第三个查询($$$4$$$)正确答案是$$$-1$$$,火箭正确答案:$$$-1$$$;
第四个查询($$$5$$$)正确答案是$$$-1$$$,火箭错误回答:$$$1$$$;
对于第五个查询 ($$$3$$$),正确和错误的答案是 $$$0$$$。