P14441 [JOISC 2013] 信息传递 / Messenger

本题仅允许使用 C++ 提交。因为需要较新版本的编译器，也请不要使用 `C++14 (GCC 9)`。 洛谷不允许提交两个代码分别运行，所以需要你在提交时把代码合并。与原题不一样的是，你不需要提交两个文件，只需要实现题面中的四个函数。模板代码如下。 ```cpp // 这里可以放你需要的头文件 // 这里可以放你需要的全局变量，注意 A 和 B 不共享这些变量，但是 A 的两个函数共享，B 的两个函数共享 extern "C" void InitA(int T, int X); extern "C" int GameA(int I, int J); extern "C" void InitB(int T); extern "C" int GameB(int I, int J); ``` 保证若无非法操作，交互库占用内存小于 2MB，占用时间小于 50ms。

入选日本信息学奥林匹克竞赛（JOI）代表队的 A 君和 B 君，为了提高信息处理技术，决定与信息学奥林匹克日本委员会的 K 理事长进行一场“信使游戏”。以下是该游戏的规则。 A 君和 B 君被分别隔离在不同的房间中，如图所示。A 君、B 君和 K 理事长的房间内各设有一部内线电话，但只有 K 理事长可以拨打电话。除此之外的其他联系方式均被切断，除非接到指示，否则 A 君和 B 君不得离开房间。 模式图： ```text A 君的房间 | 长走廊 | K 理事长的房间 | 长走廊 | B 君的房间 ``` 游戏开始时，K 理事长通过电话告诉 A 君一个正整数 $X$。游戏的目的是在 A 君和 B 君不进行直接联系的情况下，由 A 君将 $X$ 的值正确传达给 B 君。 K 理事长的房间内有一个 $4 \times 4$ 的网格。将第 $i$ 行第 $j$ 列的格子表示为 $(i, j)$（$1 \le i \le 4, 1 \le j \le 4$）。格子 $(1, 1)$ 为左上角，$(1, 4)$ 为右上角，$(4, 1)$ 为左下角，$(4, 4)$ 为右下角。游戏开始时，一枚棋子会被放置在某个格子上。此后，K 理事长不会改变棋子的位置。 接下来，K 理事长会反复通过电话呼叫 A 君或 B 君到他的房间。每当 A 君或 B 君来到 K 理事长的房间时，必须将棋子向上下左右四个方向中的任意一个相邻格子移动。移动棋子后，A 君或 B 君返回各自的房间。如果 B 君来到 K 理事长的房间时已经知道了 $X$ 的值，则可以选择不移动棋子，而是直接向 K 理事长回答 $X$ 的值。如果回答的 $X$ 值正确，则判定为获胜，否则判定为失败。 K 理事长呼叫 A 君或 B 君的时机是不规则的，A 君和 B 君不知道 K 理事长呼叫两人的顺序。但是，K 理事长在游戏开始时已经决定了呼叫顺序，并且保证 K 理事长不会连续呼叫同一人超过 $100$ 次。如果在 K 理事长总共呼叫 A 君和 B 君 $10000$ 次后，A 君或 B 君回到各自房间时 B 君仍未回答 $X$ 的值，则判定为失败并结束游戏。 --- 本处与本题评测时有略微不同。 ## 实现细节 你必须使用同一种编程语言提交两个文件。 ### 第一个文件：`playerA.c` 或 `playerA.cpp` 该文件实现了 A 君的策略，必须实现以下例程： - `void InitA(int T, int X)` - 该例程在最开始仅被调用一次。 - 参数 $T$ 为子任务编号。 - 参数 $X$ 是 A 君需要传达给 B 君的正整数。 - `int GameA(int I, int J)` - 当 A 君被呼叫到 K 理事长的房间时，该例程会被调用。 - 参数 $I, J$ 表示 A 君来到房间时棋子所在的格子 $(I, J)$，满足 $1 \le I \le 4$ 且 $1 \le J \le 4$。 - 该例程**必须**返回整数 $-1, -2, -3, -4$ 中的任意一个。如果返回其他值，则判定为失败 [1] 并终止程序运行。这些返回值代表 A 君执行以下操作： - $-1$：将棋子移动到上方的格子 $(I - 1, J)$。 - $-2$：将棋子移动到下方的格子 $(I + 1, J)$。 - $-3$：将棋子移动到左方的格子 $(I, J - 1)$。 - $-4$：将棋子移动到右方的格子 $(I, J + 1)$。 - 如果指定的移动导致棋子移出棋盘，则判定为失败 [2] 并终止程序运行。 ### 第二个文件：`playerB.c` 或 `playerB.cpp` 该文件实现了 B 君的策略，必须实现以下例程： - `void InitB(int T)` - 该例程在最开始仅被调用一次。 - 参数 $T$ 为子任务编号。 - `int GameB(int I, int J)` - 当 B 君被呼叫到 K 理事长的房间时，该例程会被调用。 - 参数 $I, J$ 表示 B 君来到房间时棋子所在的格子 $(I, J)$，满足 $1 \le I \le 4$ 且 $1 \le J \le 4$。 - 该例程**必须**返回整数 $-1, -2, -3, -4$ 中的任意一个，或者一个正整数 $Y$。如果返回其他值，则判定为失败 [3] 并终止程序运行。这些返回值代表 B 君执行以下操作： - $-1$：将棋子移动到上方的格子 $(I - 1, J)$。 - $-2$：将棋子移动到下方的格子 $(I + 1, J)$。 - $-3$：将棋子移动到左方的格子 $(I, J - 1)$。 - $-4$：将棋子移动到右方的格子 $(I, J + 1)$。 - 正整数 $Y$：向 K 理事长回答 $X$ 的值为 $Y$。此时，若 $X = Y$ 则判定为获胜，否则判定为失败 [5] 并终止程序运行。 - 如果指定的移动导致棋子移出棋盘，则判定为失败 [4] 并终止程序运行。 ### 重要限制与说明 - 例程 `GameA` 和 `GameB` 不会被其中一方连续调用超过 $100$ 次。 - 如果在 `GameA` 和 `GameB` 总共被调用 $10000$ 次时 `GameB` 仍未返回正整数，则判定为失败 [6] 并终止程序运行。 - 你可以自由实现其他辅助例程或声明全局变量。但由于提交的两个程序会与评分程序链接成一个可执行文件，因此**必须将每个文件中的所有全局变量和内部例程声明为 `static`**，以避免与其他文件产生冲突。 - 在评分时，该程序会作为 A 君侧和 B 君侧两个进程运行，因此 A 君侧和 B 君侧**无法共享**程序中的全局变量。 - 你的提交**不得**通过标准输入输出或其他任何方式进行交互。 --- ## 编译与运行方法 用于测试程序的评分程序示例包含在可从竞赛网站下载的压缩包中。该压缩包中也包含了必须提交的文件示例。 评分程序示例由一个文件组成，即 `grader.c` 或 `grader.cpp`。要测试编写的程序，请执行以下命令： - **C 语言**：`gcc -O2 -lm grader.c playerA.c playerB.c -o grader` - **C++ 语言**：`g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader` 编译成功后，将生成名为 `grader` 的可执行文件。 **请注意**：实际的评分程序与示例评分程序不同。示例评分程序作为单个进程启动，从标准输入读取数据，并将结果输出到标准输出。 --- 在本题真正评测时，你可以理解评测机仍然会按照类似两个程序一样运行，但是在一个进程中不会运行 A 君的两个函数和或 B 君的两个函数。

注意这是评测器输入格式。 评分程序示例从标准输入读取以下内容： - 第 1 行包含整数 $T, X, I_0, J_0$，以空格分隔，分别表示： - 子任务编号 $T$ - A 君需要传达给 B 君的整数 $X$ - 游戏开始时棋子的位置 $(I_0, J_0)$ - 第 2 行包含一个长度恰好为 10 000 的字符串，由字符 `A` 和 `B` 组成。若第 $k$ 个字符 ($1 \le k \le 10 000$) 为 `A` 或 `B`，则表示在 `InitA` 和 `InitB` 调用后，第 $k$ 次调用的例程分别为 `GameA` 或 `GameB`。

注意这是示例评测器输格式。 如果程序正常结束，评分程序示例会将以下信息输出到标准输出： - 如果获胜，输出 `Accepted`。 - 如果失败，根据“实现细节”一节中提到的编号输出失败类型，例如 `Wrong Answer [1]`。 - 此外，对于失败 [5]，会同时输出正确的 $X$ 值以及 `GameB` 返回的正整数 $Y$ 的值，格式为 `Wrong Answer [5] : X = 2, Y = 3`。

| A 君侧 | | B 君侧 | | |--------|--------|--------|--------| | 调用 | 返回值 | 调用 | 返回值 | | `InitA(2, 6)` | | `InitB(2)` | | | `GameA(1, 1)` | `-2` | | | | | | `GameB(2, 1)` | `-4` | | | | `GameB(2, 2)` | `-2` | | `GameA(3, 2)` | `-3` | | | | `GameA(3, 1)` | `-1` | | | | | | `GameB(2, 1)` | `6` | --- ## 数据范围 - 所有输入数据满足：$1 \le X \le 1 000 000 000$ ## 子任务 ### 子任务 1 [20 分] - 满足 $T = 1$。 - 首先被呼叫到 K 理事长房间的是 A 君，且 A 君和 B 君交替被呼叫。即在 `InitA` 和 `InitB` 调用后，例程按 `GameA, GameB, GameA, GameB, ...` 的顺序被调用。 ### 子任务 2 [20 分] - 满足 $T = 2$。 - 游戏开始时棋子的位置为 $(I_0, J_0) = (1, 1)$。即在 `InitA` 和 `InitB` 调用后，首先以 $I = 1, J = 1$ 为参数调用 `GameA` 或 `GameB`。 ### 子任务 3 [60 分] - 满足 $T = 3$。 --- 题目来源：。 翻译来源：[QOJ](https://qoj.ac/problem/1419/statement/zh_cn)。