{"problem":{"name":"C. Guess two numbers","description":{"content":"**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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1007C"},"statements":[{"statement_type":"Markdown","content":"**This is an interactive problem.**\n\nVasya 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:\n\n1.  $x$ is less than $a$;\n2.  $y$ is less than $b$;\n3.  $x$ is greater than $a$ or $y$ is greater than $b$.\n\nVasya 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)$.\n\nHelp Vitya win in no more than $600$ rounds.\n\n## Input\n\nThe first line contains a single integer $n$ ($1 \\leq n \\leq 10^{18}$) — the upper limit of the numbers.\n\n## Interaction\n\nFirst, you need to read the number $n$, after that you can make queries.\n\nTo make a query, print two integers: $x$ and $y$ ($1 \\leq x, y \\leq n$), then _flush_ the output.\n\nAfter each query, read a single integer $ans$ ($0 \\leq ans \\leq 3$).\n\nIf $ans > 0$, then it is the number of the phrase said by Vasya.\n\nIf $ans = 0$, it means that you win and your program should terminate.\n\nIf you make more than $600$ queries or make an incorrect query, you will get _Wrong Answer_.\n\nYour solution will get _Idleness Limit Exceeded_, if you don't print anything or forget to _flush_ the output.\n\nTo _flush_ you need to do the following right after printing a query and a line end:\n\n*   _fflush(stdout)_ in C++;\n*   _System.out.flush()_ in Java;\n*   _stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   For other languages see documentation.\n\n**Hacks format**\n\nFor hacks, use the following format:\n\nIn the first line, print a single integer $n$ ($1 \\leq n \\leq 10^{18}$) — the upper limit of the numbers.\n\nIn the second line, print two integers $a$ and $b$ ($1 \\leq a, b \\leq n$) — the numbers which Vasya thought of.\n\nIn the third line, print a single integer $m$ ($1 \\leq m \\leq 10^5$) — the number of instructions for the interactor.\n\nIn 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$.\n\nWhile 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.\n\nFor example, the sample test data file contains the following:\n\n5\n2 4\n2\n2 5 1 1 2\n4 1 2 3 3\n\n[samples]\n\n## Note\n\nLet's analyze the sample test. The chosen numbers are $2$ and $4$. The interactor was given two instructions.\n\nFor 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$.\n\nFor the query $(3, 4)$, it can return only $3$.\n\nFor 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$.\n\nFor 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$.\n\nIn the fifth query $(2, 4)$, the numbers are guessed correctly, the player wins.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"*这是一个交互式问题。*\n\nVasya 和 Vitya 玩一个游戏。Vasya 想了两个整数 $a$ 和 $b$，范围在 $1$ 到 $n$ 之间，Vitya 试图猜出它们。每一轮，Vitya 告诉 Vasya 两个数 $x$ 和 $y$（范围在 $1$ 到 $n$ 之间）。如果 $x = a$ 且 $y = b$，则 Vitya 获胜。否则，Vasya 必须说出以下三个短语之一：\n\nVasya 不能说谎，但如果多个短语同时成立，他可以选择任意一个。例如，如果 Vasya 想的数是 $2$ 和 $4$，那么对于查询 $(3, 4)$，他会回答短语 $3$；对于查询 $(1, 5)$，他可以选择回答短语 $1$ 或短语 $3$。\n\n请帮助 Vitya 在不超过 $600$ 轮内获胜。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n首先，你需要读取数字 $n$，之后你可以进行查询。\n\n要进行一次查询，请输出两个整数：$x$ 和 $y$ ($1 lt.eq x, y lt.eq n$)，然后 _刷新_ 输出。\n\n每次查询后，读取一个整数 $ans$ ($0 lt.eq ans lt.eq 3$)。\n\n如果 $ans > 0$，则表示 Vasya 说出的短语编号。\n\n如果 $ans = 0$，表示你猜中了，程序应立即终止。\n\n如果你进行了超过 $600$ 次查询或进行了非法查询，你将获得 _Wrong Answer_。\n\n如果你没有输出任何内容或忘记 _刷新_ 输出，你的程序将获得 _Idleness Limit Exceeded_。\n\n要 _刷新_ 输出，你需要在打印查询和换行后立即执行以下操作：\n\n*Hack 格式*\n\n对于 Hack，使用以下格式：\n\n第一行打印一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n第二行打印两个整数 $a$ 和 $b$ ($1 lt.eq a, b lt.eq n$) —— Vasya 想的两个数。\n\n第三行打印一个整数 $m$ ($1 lt.eq m lt.eq 10^5$) —— 交互器的指令数量。\n\n接下来的 $m$ 行，每行打印五个整数：$x_i$, $y_i$, $r^(12)_i$, $r^(13)_i$, 和 $r^(23)_i$ ($1 lt.eq x_i, y_i lt.eq n$)，其中 $r^(S T)_i$ 等于 $S$ 或 $T$。\n\n当回答查询 $x \\ y$ 时，交互器找到一个 $i$（从 $1$ 到 $n$），使得 $| x -x_i | + | y -y_i |$ 最小。如果有多个 $i$ 满足条件，则选择最小的 $i$。然后交互器根据该指令回答查询，但如果存在两个可选短语 $S$ 和 $T$，则选择 $r^(S T)_i$。\n\n例如，样例测试数据文件包含以下内容：\n\n让我们分析样例测试。所选数字是 $2$ 和 $4$。交互器被给予了两条指令。\n\n对于查询 $(4, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第二条，因此交互器返回 $a^(23)_2 = 3$。\n\n对于查询 $(3, 4)$，它只能返回 $3$。\n\n对于查询 $(3, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第一条（因为在值相等时优先选择编号最小的），因此交互器返回 $a^(23)_1 = 2$。\n\n对于查询 $(1, 5)$，它可以返回 $1$ 或 $3$。在两条指令中选择第一条，因此交互器返回 $a^(13)_1 = 1$。\n\n在第五次查询 $(2, 4)$ 时，数字被正确猜出，玩家获胜。\n\n## Input\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n## Interaction\n\n首先，你需要读取数字 $n$，之后你可以进行查询。要进行一次查询，请输出两个整数：$x$ 和 $y$ ($1 lt.eq x, y lt.eq n$)，然后 _刷新_ 输出。每次查询后，读取一个整数 $ans$ ($0 lt.eq ans lt.eq 3$)。如果 $ans > 0$，则表示 Vasya 说出的短语编号。如果 $ans = 0$，表示你猜中了，程序应立即终止。如果你进行了超过 $600$ 次查询或进行了非法查询，你将获得 _Wrong Answer_。如果你没有输出任何内容或忘记 _刷新_ 输出，你的程序将获得 _Idleness Limit Exceeded_。要 _刷新_ 输出，你需要在打印查询和换行后立即执行以下操作：\n\n_fflush(stdout)_ 在 C++ 中；\n_System.out.flush()_ 在 Java 中；\n_stdout.flush()_ 在 Python 中；\n_flush(output)_ 在 Pascal 中；\n其他语言请参阅文档。\n\n*Hack 格式*\n\n对于 Hack，使用以下格式：\n\n第一行打印一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n第二行打印两个整数 $a$ 和 $b$ ($1 lt.eq a, b lt.eq n$) —— Vasya 想的两个数。\n\n第三行打印一个整数 $m$ ($1 lt.eq m lt.eq 10^5$) —— 交互器的指令数量。\n\n接下来的 $m$ 行，每行打印五个整数：$x_i$, $y_i$, $r^(12)_i$, $r^(13)_i$, 和 $r^(23)_i$ ($1 lt.eq x_i, y_i lt.eq n$)，其中 $r^(S T)_i$ 等于 $S$ 或 $T$。\n\n当回答查询 $x \\ y$ 时，交互器找到一个 $i$（从 $1$ 到 $n$），使得 $| x -x_i | + | y -y_i |$ 最小。如果有多个 $i$ 满足条件，则选择最小的 $i$。然后交互器根据该指令回答查询，但如果存在两个可选短语 $S$ 和 $T$，则选择 $r^(S T)_i$。\n\n例如，样例测试数据文件包含以下内容： \n\n5\n2 4\n2\n2 5 1 1 2\n4 1 2 3 3\n\n[samples]\n\n## Note\n\n让我们分析样例测试。所选数字是 $2$ 和 $4$。交互器被给予了两条指令。\n\n对于查询 $(4, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第二条，因此交互器返回 $a^(23)_2 = 3$。\n\n对于查询 $(3, 4)$，它只能返回 $3$。\n\n对于查询 $(3, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第一条（因为在值相等时优先选择编号最小的），因此交互器返回 $a^(23)_1 = 2$。\n\n对于查询 $(1, 5)$，它可以返回 $1$ 或 $3$。在两条指令中选择第一条，因此交互器返回 $a^(13)_1 = 1$。\n\n在第五次查询 $(2, 4)$ 时，数字被正确猜出，玩家获胜。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^{18} $.  \nLet $ (a, b) \\in \\{1, \\dots, n\\}^2 $ be the hidden pair, unknown to the solver.  \n\n**Query Interface**  \nIn each round, the solver outputs a query $ (x, y) \\in \\{1, \\dots, n\\}^2 $.  \nThe oracle responds with:  \n- $ \\text{ans} = 0 $ if $ x = a $ and $ y = b $ (win condition),  \n- $ \\text{ans} = 1 $ if $ x = a $ and $ y \\neq b $,  \n- $ \\text{ans} = 2 $ if $ x \\neq a $ and $ y = b $,  \n- $ \\text{ans} = 3 $ if $ x \\neq a $ and $ y \\neq b $.  \n\n**Constraint**  \nThe solver must determine $ (a, b) $ in at most 600 queries.  \n\n**Objective**  \nFind $ (a, b) $ using adaptive queries, such that for each query $ (x, y) $, the response $ \\text{ans} \\in \\{0,1,2,3\\} $ is generated according to the above rules, and termination occurs upon receiving $ \\text{ans} = 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1007C","tags":["binary search","interactive"],"sample_group":[["5\n3\n3\n2\n1\n0","4 3\n3 4\n3 3\n1 5\n2 4"]],"created_at":"2026-03-03 11:00:39"}}