这是一个交互问题。
Vasya 和 Vitya 玩游戏。 Vasya 想到了从 $$$1$$$ 到 $$$n$$$ 的两个整数 $$$a$$$ 和 $$$b$$$,Vitya 尝试猜测它们。每一轮他都会告诉 Vasya 从 $$$1$$$ 到 $$$n$$$ 的两个数字 $$$x$$$ 和 $$$y$$$。如果 $$$x=a$$$ 且 $$$y=b$$$ 则 Vitya 获胜。否则瓦夏必须说出以下三个短语之一:
1. $$$x$$$ 小于 $$$a$$$;
2. $$$y$$$ 小于 $$$b$$$;
3. $$$x$$$ 大于 $$$a$$$ 或 $$$y$$$ 大于 $$$b$$$。
Vasya 不能说谎,但如果多个短语为真,他可以选择其中任何一个。例如,如果 Vasya 想到了数字 $$$2$$$ 和 $$$4$$$,那么他可以用短语 $$$3$$$ 来回答查询 $$$(3, 4)$$$,并且他可以用短语 $$$1$$$ 或短语 $$$3$$$ 来回答查询 $$$(1, 5)$$$。
帮助 Vitya 在不超过 $$$600$$$ 回合内获胜。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — 数字的上限。
互动
首先需要读取数字$$$n$$$,然后才能进行查询。
要进行查询,请打印两个整数:$$$x$$$ 和 $$$y$$$ ($$$1 \leq x, y \leq n$$$),然后刷新输出。
每次查询后,读取单个整数 $$$ans$$$ ($$$0 \leq ans \leq 3$$$)。
如果 $$$ans > 0$$$,则它是 Vasya 所说的短语的编号。
如果 $$$ans = 0$$$,则意味着您获胜并且您的程序应该终止。
如果您的查询超过 $$$600$$$ 或查询不正确,您将得到错误答案。
如果您不打印任何内容或忘记刷新输出,您的解决方案将超出空闲限制。
要刷新,您需要在打印查询和行结束后立即执行以下操作:
- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 对于其他语言,请参阅文档。
黑客格式
对于 hack,请使用以下格式:
在第一行中,打印单个整数 $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — 数字的上限。
在第二行中,打印两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n$$$)——Vasya 想到的数字。
在第三行中,打印单个整数 $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — 交互器的指令数。
在接下来的 $$$m$$$ 行中,打印五个整数:$$$x_i$$$、$$$y_i$$$、$$$r^{12}_i$$$、$$$r^{13}_i$$$ 和 $$$r^{23}_i$$$ ($$$1 \leq x_i, y_i \leq n$$$),其中 $$$r^{ST}_i$$$ 等于数字 $$$S$$$ 或数字 $$$T$$$。
在回答查询 $$$x\,\, y$$$ 时,交互器找到从 $$$1$$$ 到 $$$n$$$ 的数字 $$$i$$$,其最小值 $$$|x-x_i| + |y-y_i|$$$。如果可以选择多个数字,则优先选择最少 $$$i$$$。然后交互者回答查询,但如果可以给出两个短语 $$$S$$$ 和 $$$T$$$,则选择 $$$r^{ST}_i$$$。
例如,示例测试数据文件包含以下内容:
示例
输入 #1
5 3 3 2 1 0
输出 #1
4 3 3 4 3 3 1 5 2 4
注意
我们来分析一下样本测试。所选数字为 $$$2$$$ 和 $$$4$$$。向交互者发出两条指令。
对于查询 $$$(4, 3)$$$,它可以返回 $$$2$$$ 或 $$$3$$$。在这两条指令中,选择了第二条,因此交互器返回 $$$a^{23}_2=3$$$。
对于查询$$$(3, 4)$$$,它只能返回$$$3$$$。
对于查询 $$$(3, 3)$$$,它可以返回 $$$2$$$ 或 $$$3$$$。在这两条指令中,选择第一个(因为在值相等的情况下,首选数量最少的指令),因此交互器返回 $$$a^{23}_1=2$$$。
对于查询 $$$(1, 5)$$$,它可以返回 $$$1$$$ 或 $$$3$$$。在两条指令中,选择第一条,因此交互器返回 $$$a^{13}_1=1$$$。
在第五个查询 $$$(2, 4)$$$ 中,数字被猜对,玩家获胜。