#P15942. [JOI Final 2026] 赌场 / Casino
[JOI Final 2026] 赌场 / Casino
背景
评测说明(请仔细阅读)
- 不要 。
- 请使用 。
题目描述
这是一道通信题。本题中,交互库是非自适应的。
Azzurro 和 Bordeaux 是一对在意大利游览赌场的伴侣,他们决定玩一个由荷官 Chiaro 提议的游戏。
在这个游戏中,信息通过一个 的网格 () 进行传递。网格的行从上到下编号为 到 ,列从左到右编号为 到 。 行号为 、列号为 的单元格记作 。
在这个游戏中,Azzurro 和 Bordeaux 被隔离在不同的房间里。他们将进行 轮游戏。第 轮 () 的过程如下。
- Azzurro 从 Chiaro 那里收到一个整数 、一个整数 ()、一张写有长度为 且由 'A' 和 'B' 组成的字符串 的卡片,以及一个单元格全是白色的 网格。
- Azzurro 将 个单元格中的每一个涂成蓝色或红色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 都看不见的情况下执行以下操作。 (a) 他选择一条从 到 的路径,移动方式仅限重复向相邻的下方或右方单元格移动。 (b) 对于路径上的每个单元格,如果该单元格颜色为蓝色,他将其重涂为红色;如果颜色为红色,他将其重涂为蓝色。
- Bordeaux 从 Chiaro 那里收到一张写有整数 和 的卡片以及该网格。
- Bordeaux 在一张纸上写下一个长度为 且由 A 和 B 组成的字符串。如果写下的字符串与 匹配,则 Azzurro 和 Bordeaux 获胜。
编写程序实现 Azzurro 和 Bordeaux 在此游戏中获胜的策略。关于此任务的评分,请参阅“评分”。
实现细节
你需要提交两个文件。
第一个文件是 。它应该实现 Azzurro 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 。
std::vector<std::vector<int>> Azzurro(int N, int L, std::string S)
该函数被调用 次。第 次调用 () 对应于游戏第 轮的过程 1 和 2。
- 参数 是第 轮过程 1 中交给 Azzurro 的卡片上写的整数 。
- 参数 是第 轮过程 1 中交给 Azzurro 的卡片上写的整数 。
- 参数 是第 轮过程 1 中交给 Azzurro 的卡片上写的字符串 。
对于每次 Azzurro 函数调用,你的程序必须返回一个 的二维数组 ,其每个元素均为 或 。如果不满足此条件,你的程序将被判定为 Wrong Answer [1]。
- 如果 (),表示单元格 涂成蓝色。
- 如果 (),表示单元格 涂成红色。
第二个文件是 。它应该实现 Bordeaux 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 。
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T)
该函数在 Azzurro 每次完成网格涂色后被调用。该函数总共被调用 次。第 次调用 () 对应于游戏第 轮的过程 4 和 5。
- 参数 是第 轮过程 4 中交给 Bordeaux 的卡片上写的整数 。
- 参数 是第 轮过程 4 中交给 Bordeaux 的卡片上写的整数 。
- 参数 是对应于第 轮过程 4 中交给 Bordeaux 的网格的 二维数组。如果 ,则单元格 () 的颜色为蓝色;如果 ,则为红色。
对于每次 Bordeaux 函数调用,你的程序必须返回一个长度为 且由 '' 和 '' 组成的字符串 s。如果不满足此条件,你的程序将被判定为 Wrong Answer [2]。
重要注意事项
- 你的程序可以实现其他用于内部使用的函数,或使用全局变量。提交的文件将与评测程序(grader)一同编译,并生成一个单一的可执行文件。所有全局变量和内部函数应声明在匿名命名空间中,以避免与其他文件冲突。在评测时,它将作为 Azzurro 和 Bordeaux 两个进程执行。Azzurro 进程和 Bordeaux 进程不能共享全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方法与其他文件通信。但是,你的程序可以向标准错误输出调试信息。
编译与测试运行
你可以从竞赛网页下载一个压缩文件,其中包含用于测试程序的示例评测程序。该压缩文件还包含你程序的示例源文件。
示例评测程序是文件 。为了测试你的程序,请将 、、、、 放在同一个目录下,并运行以下命令来编译你的程序。
g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp
或者,你可以运行压缩文件中包含的 。在这种情况下,运行以下命令来编译你的程序。
./compile.sh
编译成功后,将生成可执行文件 grader。
注意,实际的评测程序与示例评测程序不同。示例评测程序将作为单个进程执行,它将从标准输入读取输入数据并将结果写入标准输出。
在实际的评测程序中,Chiaro 选择的路径是提前固定的。也就是说,在调用你提交的程序中的 和 函数之前,Chiaro 选择的路径就已经确定了。
输入格式
示例评测程序从标准输入读取以下数据。
这里, () 是一个长度为 的字符串,恰好包含 个 '' 和 个 ''。该字符串表示 Chiaro 在第 轮中选择的路径,该路径从 开始,通过重复向相邻的下方或右方单元格移动到达 。具体来说,从 开始,对于每个 ,如果 的第 个字符是 '',则向下方相邻单元格移动;如果是 '',则向右方相邻单元格移动。重复此过程最终到达 。
输出格式
示例评测程序将以下信息输出到标准输出(引号为了清晰起见)。
- 如果你的程序被判定为正确,它会写出 的值,例如 “”。关于 的值,请参阅“评分”。
- 如果你的程序被判定为任何类型的 Wrong Answer,示例评测程序会将其类型写为 “Wrong Answer [1]”。
如果你的程序满足多种类型的 Wrong Answer 条件,示例评测程序仅报告其中一种。当满足其中一个错误答案条件时,示例评测程序可能会终止执行。
提示
样例交互
以下是示例评测程序的样例输入及对应的函数调用。
输入
2 2
1
B
RD
3
ABB
DR
样例函数调用
| 函数调用 | 返回值 |
|---|---|
该样例输入包含 轮,每轮使用一个 的网格 ()。在这个例子中,第一轮过程如下。
-
Azzurro 将 (,) 和 (,) 涂成蓝色,将 (,) 和 (,) 涂成红色。然后他将网格交给 Chiaro。
-
Chiaro 在 Azzurro 和 Bordeaux 看不见的情况下执行以下操作。
(a) 他选择路径 (,) (,) (,) 作为从 (,) 到 (,) 的路径,移动方式仅限重复向相邻的下方或右方单元格移动。
(b) 对于这条路径上的三个单元格 (,), (,), (,),他改变它们的颜色。结果,(,), (,), (,) 的颜色分别变为蓝色、红色和蓝色。
-
Bordeaux 可以通过在纸上写下 "B" 来赢得本轮。
第二轮过程如下。
-
Azzurro 将所有单元格涂成蓝色。然后他将网格交给 Chiaro。
-
Chiaro 在 Azzurro 和 Bordeaux 看不见的情况下执行以下操作。
(a) 他选择路径 (,) (,) (,) 作为从 (,) 到 (,) 的路径,移动方式仅限重复向相邻的下方或右方单元格移动。
(b) 对于这条路径上的三个单元格 (,), (,), (,),他改变它们的颜色。结果,(,), (,), (,) 的颜色都变为红色。
-
Bordeaux 可以通过在纸上写下 "ABB" 来赢得本轮。
注意,此样例输入不满足问题的限制条件。可以从竞赛网站下载的文件 对应于样例输入 1。从竞赛网站下载的文件 是一个满足限制条件的样例输入。
数据范围
所有输入数据满足以下条件。
- 。
- 。
- ()。
- () 均为整数。
- () 是长度为 且由 '' 和 '' 组成的字符串。
- () 是长度为 的字符串,恰好包含 个 '' 和 个 ''。
评分
如果你的程序在任何测试用例中被判定为任何类型的 Wrong Answer [1] 或 Wrong Answer [2](见实现细节)、超过时间限制、超过内存限制或运行错误,你的分数为 分。
否则,设 为该任务所有测试用例中以下值的最小值。你的分数按以下表格计算。
- 使得 Azzurro 和 Bordeaux 在所有满足 的轮次中均获胜的最大 值。但是,如果他们在测试用例中的所有轮次均获胜,我们令 。
| 的值 | 你的分数 |
|---|---|
| 分 | |
| 分 | |
| 分 | |
| 分 |