← 返回题目列表

AtCoder · joig2026final_d

D. 赌场

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

配点: 100 点

分发文件

如何使用AtCoder提交 请包含

  • Azzurro.h, Bordeaux.h 并实现问题陈述中指定的功能。
  • 不要使用标准输入/输出或文件输入/输出。

問題文

Azzurro 和 Bordeaux 参观意大利赌场。 2 该小组决定玩庄家 Chiaro 建议的游戏。

在这个游戏中,N 行 N 列 (N = 8传达信息。在网格的每一行中,从顶部开始 每列从左到右显示一直到 0 减去 N - 1 的行号。 这些列的编号最大为 0 减去 N - 1 。行号是 r 列号是 c 写为 (r, c) 。

在这个游戏中,Azzurro 和 Bordeaux 被隔离在不同的房间里。 Q 次转 执行。i 回目 (1 \leqq i \leqq Q)的回合进行如下。

  1. Azzurro 是来自 Chiaro 的整数。 N, L_i (1 \leqq L_i \leqq 51)和'A' 和 'B包括 ' L_i 字符串 给出了 S_i ,所有方块都涂成白色。 N 行 N 接收列的网格。
  2. 蓝色是 对于N^2 单元格,将每个单元格涂成蓝色或红色。之后,将方块交给Chiaro。
  3. Chiaro 在 Azzurro 和 Bordeaux 看不见的地方执行以下操作。
    1. 仅重复移动到下方或右侧的相邻方块。 到达 (0, 0) 减去 (N - 1, N - 1) 的路线 1 选择一项。
    2. 对于路线上的所有方格,如果该方格被漆成蓝色,则将其重新漆成红色,如果其被漆成红色,则将其重新漆成蓝色。
  4. Bordeaux 是来自 Chiaro 的整数。 您将收到一张卡片和一个写有 N, L_i 的方块。
  5. 波尔多是 'A' 和 'B包括 ' L_i 在纸上写下一串字符。你写的字符串是 如果匹配 S_i ,则 Azzurro 和 Bordeaux 获胜。

实施蓝衣军团和波尔多队赢得这场比赛的策略。关于本次作业的评分方法,请参阅 请参阅採点基準节。

实施细节

你 2 您必须提交两个文件。

1 第二个文件是 名称是 Azzurro.cpp 。该文件实现了Azzurro的策略,必须实现以下功能。另外,#include 通过预处理器指令 加载 Azzurro.h 。

  • std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) 该函数求和 已致电 Q 次。 对i 回目 (1 \leqq i \leqq Q) 在游戏中被调用。 i 这对应于回合的步骤 1. 和步骤 2.。
    • 引数 N 是 您也可以写 i Azzurro 在他的回合的第 1 步中收到的卡上写的整数。 N 是。
    • 引数 L 是 您也可以写 i Azzurro 在他的回合的第 1 步中收到的卡上写的整数。 L_i 是。
    • 引数 S 是 您也可以写 i Azzurro 在第二回合的步骤 1 中收到的卡上写的字符串。 对于 S_i 是。
    関数 Azzurro 可以得到第 1 调用,每个元素 0 或 至少 1 是 N \times N 可以得到第 2 次元配列 \texttt{x} 。如果这还不满足,不正解 [1] 已确定。 调用
    • \texttt{x}[\texttt{r}][\texttt{c}] = 0 (0 \leqq \texttt{r} \leqq N - 1,0 \leqq \texttt{c} \leqq N - 1),质量 代表蓝色的绘画 (\texttt{r}, \texttt{c}) 。 代表红色绘画
    • \texttt{x}[\texttt{r}][\texttt{c}] = 1 (0 \leqq \texttt{r} \leqq N - 1,0 \leqq \texttt{c} \leqq N - 1),质量 代表蓝色的绘画 (\texttt{r}, \texttt{c}) 。 名称是

2 第二个文件是 名称是 Bordeaux.cpp 。该文件实现了波尔多的策略,必须实现以下功能。另外,#include 通过预处理器指令 加载 Bordeaux.h 。

  • std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) 每次 Azzurro 完成填充一个方块时都会执行此函数。 总共 1 次 Q 次。 对i 回目 (1 \leqq i \leqq Q) 在游戏中被调用。 i 这对应于本回合的步骤 4. 和步骤 5.。
    • 引数 N 是i 波尔多在其回合的第 4 步中收到的卡片上写的整数。 N 是。
    • 引数 L 是i 波尔多在其回合的第 4 步中收到的卡片上写的整数。 L_i 是。
    • 引数 T 是i 代表波尔多在其回合的第 4 步中收到的每个方块的颜色。 它是一个 N \times N 可以得到第 2 维数组。鳟鱼 (\texttt{r}, \texttt{c}) (0 \leqq \texttt{r} \leqq N - 1,0 \leqq \texttt{c} \leqq N - 1) 的颜色是\texttt{T[r][c]} = 0 是蓝色的,\texttt{T[r][c]} = 1 为红色。 对于
    関数 Bordeaux 可以得到第 1 调用,'A' 和 'B包括 ' L_i 字符串 给出了 s 。如果这还不满足,不正解 [2] 已确定。 调用

重要说明

  • 您可以自由地实现其他函数并声明全局变量以供内部使用。 然而,已提交 2 这两个程序通过评分程序链接在一起。 1 将会有两个可执行文件,所以 每个文件中的所有全局变量和内部函数都必须在匿名命名空间中声明,以避免干扰其他文件。 计分时,蓝衣队和波尔多队均使用此程序。 由于它是作为 2 进程执行的, 程序中的全局变量不能在 Azzurro 和 Bordeaux 之间共享。
  • 您提交的程序不得以任何方式与标准输入、标准输出或其他文件交互。 但是,允许将调试信息等输出到标准错误输出。

如何编译执行

用于测试您创建的程序的示例评分程序包含在可从竞赛网站下载的存档中。该存档还包含必须提交的示例文件。

评分程序的示例是 1 由两个文件组成。该文件是 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选择的路线是预先确定的。即您提交的程序中的函数 Azzurro 和功能 在调用 Bordeaux 之前,Chiaro 将选择的路线已确定。

输入示例评分程序

示例评分程序按以下格式从标准输入读取输入。

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

在这里,R_i (1 \leqq i \leqq Q) 是 'D' 和 'R' N - 1 包含每个字符 2(N - 1) 是一个字符串。这个字符串是 i 仅重复移动到第二回合选择的下方或右侧的相邻方块。 表示到达 (0, 0) 减去 (N - 1, N - 1) 的路线。路线是 从(0, 0) 开始, 按照j = 1, 2, \cdots , 2(N - 1) 的顺序,R_i 可以得到第 j 第一个字符是 'D'如果是,则下面相邻的方块是 'R'如果是,则移动到右侧相邻的方格,重复此操作,最终可以 这是到达 (N - 1, N - 1) 的路线。

评分程序的示例输出

示例评分程序将以下信息输出到标准输出(引号实际上并未输出)。

  • 如果答案正确,L^{*} 的值为“ 输出Accepted: 26“。L^{*} 的值请参阅评分标准部分。
  • 如果答案不正确,则错误答案的类型为“Wrong Answer [1]“。

如果要执行的程序满足多个错误答案条件,则显示的错误答案类型为 1 只有一个。如果满足错误答案条件,示例评分程序可能会中途终止执行。


制約

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

  • 1 \leqq Q \leqq 30\,000.
  • N = 8.
  • 1 \leqq L_i \leqq 51 (1 \leqq i \leqq Q).
  • Q, L_i (1 \leqq i \leqq Q) 是一个整数。
  • S_i (1 \leqq i \leqq Q)是'A' 和 'B包括 ' L_i 是一个字符串。
  • R_i (1 \leqq i \leqq Q)是'D' 和 'R' N - 1 包含每个字符 2(N - 1) 是一个字符串。

採点基準

在此作业的测试用例中,1 总是不正解 [1] 或 至少不正解 [2](参见实现细节)或运行时错误(超出执行时间限制、违反内存限制、异常终止等) 0 为点。

否则,为本练习中的所有测试用例设置以下值的最小值: L^{*} ,分数如下表所示。 满足

  • L_i \leqq L 的每一回合我们获胜的最大整数 L.但是,如果测试用例中的所有回合都获胜, L = 51 。

交互示例

下面是示例评分程序读取的输入示例以及相应函数调用的示例。

入力例 1

2 2
1
B
RD
3
ABB
DR

这个输入示例是 Q \ (= 2) 匝组成, 在2 回合 N 行 N 列 (N = 2)使用网格。在这个例子中,1 回合进行如下。

  1. 蓝色是 (0, 1) 和 按字典顺序比较 (1, 0) 为蓝色, 将(0, 0) 和 按字典顺序比较 (1, 1) 涂成红色。之后,将方块交给Chiaro。 作为到达
  2. Chiaro 在 Azzurro 和 Bordeaux 看不见的地方执行以下操作。
    1. 仅重复移动到下方或右侧的相邻方块。 到达 (0, 0) 减去 (N - 1, N - 1) 的路线, 选择(0, 0) \rightarrow (0, 1) \rightarrow (1, 1) 。 在
    2. 在此路线上 3 两个方块 给出了 (0, 0), (0, 1), (1, 1) ,更改该方块中绘制的颜色。结果,(0, 0), (0, 1), (1, 1) 的颜色分别更改为蓝色、红色和蓝色。
  3. 波尔多是“B“通过将其写在纸上,您可以赢得本回合。

另外, 如果我们只为第2 回合进行如下。

  1. Azzurro 将所有方块涂成蓝色。之后,将方块交给Chiaro。 所有
  2. Chiaro 在 Azzurro 和 Bordeaux 看不见的地方执行以下操作。
    1. 仅重复移动到下方或右侧的相邻方块。 到达 (0, 0) 减去 (N - 1, N - 1) 的路线, 选择(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) 。 在
    2. 在此路线上 3 两个方块 给出了 (0, 0), (1, 0), (1, 1) ,更改该方块中绘制的颜色。结果,(0, 0), (1, 0), (1, 1) 颜色均更改为红色。
  3. 波尔多是“ABB“通过将其写在纸上,您可以赢得本回合。

这个输入示例是不满足约束请注意。在可以从竞赛网站下载的文件中,sample-01-in.txt 是一个输入示例 对应于 1 。在可以从竞赛网站下载的文件中,sample-02-in.txt满足约束。 给出了