CF1392E Omkar and Duck

这是一个交互题。 Omkar 刚刚遇到了一只鸭子！这只鸭子正在一个 $n$ 行 $n$ 列的网格上行走（$2 \leq n \leq 25$），因此网格总共有 $n^2$ 个格子。我们用 $(x, y)$ 表示第 $x$ 行第 $y$ 列的格子（从上到下、从左到右编号）。现在，鸭子位于 $(1, 1)$（左上角的格子），它想要走到 $(n, n)$（右下角的格子），每秒可以向下走 $1$ 格或向右走 $1$ 格。 由于 Omkar 觉得鸭子很有趣，他想和你玩一个基于鸭子移动的游戏。首先，对于网格中的每个格子 $(x, y)$，你需要告诉 Omkar 一个不超过 $10^{16}$ 的非负整数 $a_{x,y}$，然后 Omkar 会在该格子里放置 $a_{x,y}$ 个无聊的问题。之后，鸭子会从 $(1, 1)$ 出发，前往 $(n, n)$。在旅途中，每经过一个格子 $(x, y)$（包括起点和终点），鸭子都会吃掉该格子里的 $a_{x,y}$ 个无聊的问题。当鸭子完成旅程后，Omkar 会测量鸭子的体重，得出鸭子在旅途中吃掉的无聊问题总数 $k$，并告诉你 $k$。 你的挑战是：给定 $k$，你需要精确还原鸭子的行走路径，也就是准确告诉 Omkar 鸭子在旅途中经过了哪些格子。为了考验你的能力，Omkar 会让鸭子完成 $q$ 次不同的旅程（$1 \leq q \leq 10^3$）。注意，每次旅程都是独立的：每次旅程开始时，每个格子 $(x, y)$ 里仍然有 $a_{x,y}$ 个无聊的问题。

交互开始时，首先输入一个整数 $n$（$2 \leq n \leq 25$），表示网格的行数和列数。请读入它。 然后，你需要输出 $n$ 行，每行 $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$。 请注意，如果你输出的路径上各格子的 $a_{x,y}$ 之和等于 $k$，但路径与实际隐藏路径不同，你的解答依然是错误的！ 每输出一行后不要忘记输出换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而失败。具体方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 进行 Hack 时，首先输出一行 $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)$，且对于每个 $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 + 2 + 3 + 2 + 10 + 3 + 2 = 23$  $1 + 4 + 9 + 0 + 7 + 3 + 2 = 26$  $1 + 2 + 3 + 6 + 10 + 3 + 2 = 27$  由 ChatGPT 4.1 翻译