Guess two numbers

题意翻译

**本题是一道交互题。** 给定正整数 $n$。交互库有两个隐藏的正整数 $a,b$，满足 $1\leq a,b\leq n$。你需要通过一些询问确定 $a$ 和 $b$ 的值。每次询问你可以给出两个正整数 $1\leq x,y\leq n$，如果 $x=a$ 且 $y=b$ 那么你成功完成了任务。否则交互库会选用以下三句话中的一句回答你： 1. $x < a$； 1. $y < b$； 1. $x > a$ 或 $y > b$。 交互库不能撒谎，但如果这三句话中有不只一句话正确那么可能它回答的其中的任何一句。注意在 $(x,y)\neq (a,b)$ 的情况下，上面这三句话至少有一句是正确的。 你需要在不超过 $600$ 次询问内正确找出 $a,b$ 的值。 ### 交互细节 你首先需要从标准输入中读入一个正整数 $n(1\leq n\leq 10^{18})$ 表示各数的范围。 接下来，你需要通过向标准输出中输出来进行交互。每次你需要输出两个正整数 $x,y(1\leq x,y\leq n)$，表示你的询问。接着你需要读入一个整数 $ans(0\leq ans\leq 3)$ 表示交互库的回答： - $ans=0$ 表示你成功找出了 $a,b$ 的值，你应及时退出程序。 - $ans > 0$ 则表示你没有成功找出 $a,b$ 的值，且交互库使用了上面的第 $ans$ 句话回答你。 如果进行超过 $600$ 次询问，会被判定为 `Wrong Answer`。 **注意：** 每次输出 $x,y$ 后你都需要清空输出缓存区，否则可能会得到 `Idleness Limit Exceeded` 的结果。 ### 交互库细节 **本部分对做题来说不是必须的。** 交互库从标准输入中先读入正整数 $n(1\leq n\leq 10^{18})$ 以及待求的坐标 $a,b(1\leq a,b\leq n)$。接下来会读入一个正整数 $m(1\leq m\leq 10^5)$ 以及紧随的 $m$ 条指令，每条指令包含五个正整数 $x_i,y_i,r_i^{12},r_i^{13},r_i^{23}(1\leq x_i,y_i\leq n,r_i^{ST}\in \{S,T\})$，表示交互库的交互策略。当你询问一组 $x,y$ 时，交互库的回答策略如下： - 若 $x=a$ 且 $y=b$ 则返回 $0$； - 否则，若这个询问的答案是唯一的，交互库会直接回答；若有两个答案 $S,T$ 都合法，交互库会首先找到一个 $i$ 使得 $|x-x_i|+|y-y_i|$ 最小（若有多解取 $i$ 最小的），然后回答 $r_i^{ST}$ 的值。注意不可能有三个答案都合法的情况。 如果你要 Hack，也请采用此处的输入格式提交输入数据。样例的交互库输入如下： ``` 5 2 4 2 2 5 1 1 2 4 1 2 3 3 ```

题目描述

This is an interactive problem. Vasya and Vitya play a game. Vasya thought of two integers $ a $ and $ b $ from $ 1 $ to $ n $ and Vitya tries to guess them. Each round he tells Vasya two numbers $ x $ and $ y $ from $ 1 $ to $ n $ . If both $ x=a $ and $ y=b $ then Vitya wins. Else Vasya must say one of the three phrases: 1. $ x $ is less than $ a $ ; 2. $ y $ is less than $ b $ ; 3. $ x $ is greater than $ a $ or $ y $ is greater than $ b $ . Vasya can't lie, but if multiple phrases are true, he may choose any of them. For example, if Vasya thought of numbers $ 2 $ and $ 4 $ , then he answers with the phrase $ 3 $ to a query $ (3, 4) $ , and he can answer with the phrase $ 1 $ or phrase $ 3 $ to a query $ (1, 5) $ . Help Vitya win in no more than $ 600 $ rounds.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 10^{18} $ ) — the upper limit of the numbers.

输出格式

First, you need to read the number $ n $ , after that you can make queries. To make a query, print two integers: $ x $ and $ y $ ( $ 1 \leq x, y \leq n $ ), then flush the output. After each query, read a single integer $ ans $ ( $ 0 \leq ans \leq 3 $ ). If $ ans > 0 $ , then it is the number of the phrase said by Vasya. If $ ans = 0 $ , it means that you win and your program should terminate. If you make more than $ 600 $ queries or make an incorrect query, you will get Wrong Answer. Your solution will get Idleness Limit Exceeded, if you don't print anything or forget to flush the output. To flush you need to do the following right after printing a query and a line end: - fflush(stdout) in C++; - System.out.flush() in Java; - stdout.flush() in Python; - flush(output) in Pascal; - For other languages see documentation. Hacks format For hacks, use the following format: In the first line, print a single integer $ n $ ( $ 1 \leq n \leq 10^{18} $ ) — the upper limit of the numbers. In the second line, print two integers $ a $ and $ b $ ( $ 1 \leq a, b \leq n $ ) — the numbers which Vasya thought of. In the third line, print a single integer $ m $ ( $ 1 \leq m \leq 10^5 $ ) — the number of instructions for the interactor. In each of the next $ m $ lines, print five integers: $ x_i $ , $ y_i $ , $ r^{12}_i $ , $ r^{13}_i $ , and $ r^{23}_i $ ( $ 1 \leq x_i, y_i \leq n $ ), where $ r^{ST}_i $ equals to either number $ S $ or number $ T $ . While answering the query $ x\,\, y $ , the interactor finds a number $ i $ from $ 1 $ to $ n $ with the minimal value $ |x-x_i| + |y-y_i| $ . If multiple numbers can be chosen, the least $ i $ is preferred. Then the interactor answers to the query, but if there are two phrases $ S $ and $ T $ that can be given, then $ r^{ST}_i $ is chosen. For example, the sample test data file contains the following: `<br></br>5<br></br>2 4<br></br>2<br></br>2 5 1 1 2<br></br>4 1 2 3 3<br></br>`

输入输出样例

输入样例 #1

5
3
3
2
1
0

输出样例 #1

4 3
3 4
3 3
1 5
2 4

说明

Let's analyze the sample test. The chosen numbers are $ 2 $ and $ 4 $ . The interactor was given two instructions. For the query $ (4, 3) $ , it can return $ 2 $ or $ 3 $ . Out of the two instructions the second one is chosen, so the interactor returns $ a^{23}_2=3 $ . For the query $ (3, 4) $ , it can return only $ 3 $ . For the query $ (3, 3) $ , it can return $ 2 $ or $ 3 $ . Out of the two instructions the first one is chosen (since in case of equal values, the least number is preferred), so the interactor returns $ a^{23}_1=2 $ . For the query $ (1, 5) $ , it can return $ 1 $ or $ 3 $ . Out of the two instructions the first one is chosen, so the interactor returns $ a^{13}_1=1 $ . In the fifth query $ (2, 4) $ , the numbers are guessed correctly, the player wins.