这是一个交互问题。
Omkar 刚刚遇到了一只鸭子!鸭子在具有 $$$n$$$ 行和 $$$n$$$ 列的网格上行走 ($$$2 \leq n \leq 25$$$),因此网格总共包含 $$$n^2$$$ 个单元格。让我们用 $$$(x, y)$$$ 表示从顶部开始的第 $$$x$$$ 行和从左边开始的第 $$$y$$$ 列中的单元格。现在,鸭子位于单元格 $$$(1, 1)$$$(左上角的单元格),并且希望通过每秒向下移动 $$$1$$$ 单元格或向右移动 $$$1$$$ 单元格来到达单元格 $$$(n, n)$$$(右下角的单元格)。
因为 Omkar 认为鸭子很有趣,所以他想和你玩一个基于鸭子运动的游戏。首先,对于网格中的每个单元格$$$(x,y)$$$,您将告诉Omkar一个不超过$$$10^{16}$$$的非负整数$$$a_{x,y}$$$,然后Omkar会将$$$a_{x,y}$$$无趣的问题放入单元格$$$(x,y)$$$中。之后,鸭子将从 $$$(1, 1)$$$ 开始前往 $$$(n, n)$$$ 的旅程。对于鸭子在旅途中穿过的每个单元格 $$$(x, y)$$$(包括单元格 $$$(1, 1)$$$ 和 $$$(n, n)$$$),鸭子将吃掉该单元格中的 $$$a_{x,y}$$$ 无趣问题。鸭子完成旅程后,Omkar 将测量它们的质量,以确定鸭子在旅途中吃掉的无趣问题的总数 $$$k$$$,然后告诉您 $$$k$$$。
给定$$$k$$$,你的挑战是准确地再现鸭子的路径,即。 e.准确地告诉奥姆卡鸭子在旅途中经过了哪些细胞。为了确保您掌握这个游戏,Omkar 会让鸭子完成 $$$q$$$ 不同的旅程 ($$$1 \leq q \leq 10^3$$$)。请注意,所有旅程都是独立的:在每个旅程开始时,单元格 $$$(x, y)$$$ 仍将包含 $$$a_{x,y}$$$ 无趣的任务。
互动
交互将从包含单个整数 $$$n$$$ ($$$2 \leq n \leq 25$$$) 的行开始,即网格中的行数和列数。阅读它。
然后你的程序应该打印 $$$n$$$ 行。第 $$$x$$$ 行应包含 $$$n$$$ 整数 $$$a_{x,1}, a_{x,2}, \dotsc, a_{x,n}$$$ 满足 $$$0 \leq a_{x,y} \leq 10^{16}$$$,其中 $$$a_{x,y}$$$ 是 Omkar 应在单元格中放置的无趣问题的数量$$$(x,y)$$$。
之后,您将首先收到一个整数$$$q$$$,即鸭子将要经过的行程。随后将出现 $$$q$$$ 查询;每个查询都包含一行,其中包含一个整数 $$$k$$$,即鸭子在该旅程中遇到的无趣问题的数量。每次查询后,假设您已确定鸭子按顺序访问了单元格 $$$(x_1, y_1), (x_2, y_2), \dotsc, (x_{2n - 1}, y_{2n - 1})$$$ ($$$(x_1, y_1) = (1, 1)$$$ 和 $$$(x_{2n - 1}) 应该始终为真, y_{2n - 1}) = (n, n)$$$),则应输出 $$$2n - 1$$$ 行,以便第 $$$j$$$ 行包含两个整数 $$$x_j, y_j$$$。
请记住,如果您的路径上的总和是 $$$k$$$,但您的路径与实际的隐藏路径不同,那么您的解决方案仍然是错误的!
打印每一行后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
要破解,首先输出包含 $$$n$$$ 的行和包含 $$$q$$$ 的另一行。 $$$2 \leq n \leq 25$$$ 和 $$$1 \leq q \leq 1000$$$ 必须为真。然后,以与上述相同的格式输出鸭子所经历的 $$$q$$$ 旅程:对于每个旅程,假定鸭子按顺序访问了单元格 $$$(x_1, y_1), (x_2, y_2), \dotsc, (x_{2n - 1}, y_{2n - 1})$$$,您应该输出 $$$2n - 1$$$ 行,以便$$$j$$$ 行包含两个整数 $$$x_j, y_j$$$。 $$$(x_1, y_1) = (1, 1)$$$ 和 $$$(x_{2n - 1}, y_{2n - 1}) = (n, n)$$$ 必须为真。此外,对于每个$$$j$$$,使得$$$2 \leq j \leq 2n - 1$$$,$$$1 \leq x_j, y_j \leq n$$$ 和 $$$(x_j, y_j) = (x_{j - 1} + 1, y_{j - 1})$$$ 或 $$$(x_j, y_j) 必须为真= (x_{j - 1}, y_{j - 1} + 1)$$$。
示例
输入 #1
4 3 23 26 27
输出 #1
1 2 3 6 4 6 2 10 9 0 7 3 2 8 8 2 1 1 1 2 1 3 2 3 2 4 3 4 4 4 1 1 2 1 3 1 3 2 3 3 3 4 4 4 1 1 1 2 1 3 1 4 2 4 3 4 4 4
注意
鸭子的三趟旅程如下图所示。
$$$1 + 2 + 3 + 2 + 10 + 3 + 2 = 23$$$
$$$1 + 4 + 9 + 0 + 7 + 3 + 2 = 26$$$
$$$1 + 2 + 3 + 6 + 10 + 3 + 2 = 27$$$