← 返回题目列表

AtCoder · joi2026final_d

D. 赌场

中文机器翻译题面 查看原题

分数: 100 点

分布式文件

如何提交到AtCoder

  • 包括 Azzurro.h 和 Bordeaux.h,并实现语句中指定的功能。
  • 不要使用标准输入/输出或文件输入/输出。

问题陈述

Azzurro 和 Bordeaux 两人参观了意大利的一家赌场,决定玩庄家 Chiaro 提议的游戏。

在这个游戏中,信息是使用 N \times N 网格(N = 8))。网格的行编号为 0 to N - 1 从上到下,网格的列编号从 0 to N - 1 从左到右。具有行号的单元格 r 和列号 c 表示为 (r, c).

在这个游戏中,Azzurro 和 Bordeaux 被隔离在不同的房间里。他们会玩 Q 转。的 i第回合(1 \leq i \leq Q) 进行如下。

  1. Azzurro 从 Chiaro 收到一个整数 N,一个整数 L_i (1 \leq L_i \leq 51),一张卡片,上面有一个字符串 S_i 长度 L_i 组成 'A' 和 'B' 被写入,并且 N \times N 网格,其单元格全部为白色。
  2. Azzurro 为每个 N^2 细胞为蓝色或红色。然后他将网格交给 Chiaro。
  3. Chiaro 在 Azzurro 和 Bordeaux 的视线之外执行以下操作。
    1. 他从以下选择一条路径 (0, 0) to (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。
    2. 对于路径上的每个单元格,如果该单元格颜色为蓝色,则他将其重新绘制为红色;如果它是红色的,他就把它重新漆成蓝色。
  4. 波尔多从 Chiaro 收到一张带有整数的卡片 上面写着 N 和 L_i ,还有网格。
  5. 波尔多写入长度的字符串 L_i 组成 A 和 B 在一张纸上。如果写入的字符串匹配 S_i,蓝色军团和波尔多获胜。

编写实现 Azzurro 和 Bordeaux 策略的程序 赢得这场比赛。有关此任务的评分,请参阅 评分.

实施细节

您需要提交两个文件。

第一个文件是 Azzurro.cpp。它应该执行蓝衣军团的战略。它应该实现以下功能。该计划应包括 Azzurro.h 使用预处理指令 #include.

  • std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) 该函数被调用 Q 次。 i第次调用 (1 \leq i \leq Q) 对应于程序 1., 2.\ i-第轮游戏。
    • 参数 N 是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 N 写在在程序 1.\ 中交给 Azzurro 的卡片上 i第回合。
    • 参数 L 是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 L_i 写在在程序 1.\ 中交给 Azzurro 的卡片上 i第回合。
    • 参数 S 是字符串 S_i 写在在程序 1.\ 中交给 Azzurro 的卡片上 i第回合。
    对于每次调用该函数 Azzurro,你的程序必须返回一个 N \times N 二维数组 x,其每个元素是 0 or 1。如果不满足这个条件,你的程序被判定为 错误答案 [1].
    • If \texttt{x}[\texttt{r}][\texttt{c}] = 0 (0 \leq \texttt{r} \leq N - 1, 0 \leq \texttt{c} \leq N - 1),表明该单元格 (\texttt{r}, \texttt{c}) 为蓝色。
    • If \texttt{x}[\texttt{r}][\texttt{c}] = 1 (0 \leq \texttt{r} \leq N - 1, 0 \leq \texttt{c} \leq N - 1),表明该单元格 (\texttt{r}, \texttt{c}) 为红色。

第二个文件是 Bordeaux.cpp。它应该实施波尔多的战略。它应该实现以下功能。该计划应包括 Bordeaux.h 使用预处理指令 #include.

  • std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) 每次 Azzurro 完成网格绘制时都会调用此函数。 总共 Q 次。 i第次调用 (1 \leq i \leq Q) 对应于程序 4., 5.\ i-第轮游戏。
    • 参数 N 是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 N 写在在程序 4.\ 中给波尔多的卡上 i第回合。
    • 参数 L 是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 L_i 写在在程序 4.\ 中给波尔多的卡上 i第回合。
    • 参数 T 是 N \times N 二维数组,对应于程序 4.\ 中给出的 Bordeaux 的单元格网格 i第回合。细胞的颜色 (\texttt{r}, \texttt{c}) (0 \leq \texttt{r} \leq N - 1,0 \leq \texttt{c} \leq N - 1) 为蓝色,如果 \texttt{T[a][b]} = 0,如果 \texttt{T[a][b]} = 1.
    对于每次调用该函数 Bordeaux,您的程序必须返回一个字符串 s 长度 L_i 组成 'A' 和 'B'。如果不满足这个条件,你的程序被判定为 错误答案 [2].

重要通知

  • 您的程序可以实现其他内部使用的函数,或使用全局变量。提交的文件将使用评分器进行编译,并成为单个可执行文件。所有全局变量和内部函数都应在未命名的命名空间中声明,以避免与其他文件冲突。分级时将分Azzurro和Bordeaux两个流程执行。 Azzurro进程和Bordeaux进程不能共享全局变量。
  • 您的程序不得使用标准输入和标准输出。您的程序不得通过任何方法与其他文件通信。但是,您的程序可能会将调试信息输出到标准错误。

编译和测试运行

您可以从竞赛网页下载存档文件,其中包含用于测试您的程序的示例评分器。存档文件还包含程序的示例源文件。

示例评分器是文件 grader.cpp。为了测试您的程序,请输入 grader.cpp,Azzurro.cpp,Bordeaux.cpp,Azzurro.h,Bordeaux.h 在同一目录中,并运行以下命令来编译程序。

g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp

相反,你可以运行 compile.sh 包含在存档文件中。在这种情况下,运行以下命令来编译您的程序。

./compile.sh

编译成功后,生成可执行文件 生成 grader 。

请注意,实际评分器与示例评分器不同。示例分级器将作为单个进程执行,该进程将从标准输入读取输入数据并将结果写入标准输出。

在实际的评审评分中, Chiaro选择的路径是预先固定的。也就是说,Chiaro选择的路径是在函数之前确定的 Azzurro 和 Bordeaux 在您提交的程序中被调用。


样本分级机的输入

示例分级器从标准输入读取以下数据。

Q N 
L_1 
S_1 
R_1 
L_2 
S_2 
R_2 
\vdots 
L_Q 
S_Q 
R_Q

在这里, R_i (1 \leq i \leq Q) 是一个长度的字符串 2(N - 1) 完全由 N - 1 出现 'D' 和 N - 1 出现 'R'。该字符串代表 Chiaro 在 i第回合,从 (0, 0) 并达到 (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。具体来说,从 (0, 0),对于每个 j = 1, 2, \cdots, 2(N - 1),如果 j- 第一个字符 R_i 是 'D',移动到下面的相邻单元格;如果是'R',移动到右侧相邻的单元格。重复此过程可达到 (N - 1, N - 1).

样本分级机的输出

示例分级器将以下信息输出到标准输出(为了清楚起见,引用)。

  • 如果你的程序被判断为正确,它会写入以下值 L^{*} 作为“Accepted: 26“。对于价值 L^{*},请参阅评分。
  • 如果您的程序被判断为任何类型的错误答案,则示例评分器将其类型写为“Wrong Answer [1]".

如果您的程序满足多种类型的错误答案的条件,则示例评分器仅报告其中一种。当满足错误答案的条件之一时,样本评分者可以终止执行。


约束

所有输入数据满足以下条件。

  • 1 \leq Q \leq 30\,000.
  • N = 8.
  • 1 \leq L_i \leq 51 (1 \leq i \leq Q).
  • Q, L_i (1 \leq i \leq Q) 是整数。
  • S_i (1 \leq i \leq Q) 是一个长度的字符串 L_i 组成 'A' 和 'B'.
  • R_i (1 \leq i \leq Q) 是一个长度的字符串 2(N - 1) 完全由 N - 1 出现 'D' 和 N - 1 出现 'R'.

评分

如果你的程序被判断为任何类型 错误答案 [1] or 错误答案 [2] (请参阅实现详细信息)、超出时间限制、超出内存限制或运行时错误,在任何测试用例中,您的分数为 0 点。

否则,让 L^{*} 是此任务的所有测试用例的以下值中的最小值。您的分数计算如下表所示。

  • 的最大值 L 使得 Azzurro 和 Bordeaux 赢得所有令人满意的回合 L_i \leq L。然而,如果他们赢得了测试用例中的所有回合,我们设置 L = 51.

通讯示例

以下是示例评分器和相应函数调用的示例输入。

示例输入 1

2 2
1
B
RD
3
ABB
DR

该示例输入包括 Q \ (= 2) 轮流,并且在每一轮中 使用 N \times N 网格(N = 2)。在此示例中,第一轮进行如下。

  1. 蓝色 (0, 1) 和 (1, 0) 蓝色,和 (0, 0) 和 (1, 1) 红色。然后他将网格交给 Chiaro。
  2. Chiaro 在 Azzurro 和 Bordeaux 的视线之外执行以下操作。
    1. 他选择了路径 (0, 0) \rightarrow (0, 1) \rightarrow (1, 1) 作为路径 (0, 0) to (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。
    2. 对于三个单元格 (0, 0), (0, 1), (1, 1) 在这条路上,他改变了它们的颜色。结果,颜色 (0, 0), (0, 1), (1, 1) 分别变为蓝色、红色和蓝色。
  3. 波尔多可以通过写“来赢得本回合”B”在纸上。

第二回合进行如下。

  1. Azzurro 将所有单元格设置为蓝色。然后他将网格交给 Chiaro。
  2. Chiaro 在 Azzurro 和 Bordeaux 的视线之外执行以下操作。
    1. 他选择了路径 (0, 0) \rightarrow (1, 0) \rightarrow (1, 1) 作为路径 (0, 0) to (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。
    2. 对于三个单元格 (0, 0), (1, 0), (1, 1) 在这条路上,他改变了它们的颜色。结果,颜色 (0, 0), (1, 0), (1, 1) 全部变成红色。
  3. 波尔多可以通过写“来赢得本回合”ABB”在纸上。

请注意,此示例输入 不满足 问题的制约。该文件 sample-01-in.txt,可以从竞赛网站下载,对应于示例输入 1。该文件 sample-02-in.txt是满足约束的示例输入,可以从竞赛网站下载。