配点: 100 点
如何使用AtCoder提交
使用 C++ 时
Anna.h和 按字典顺序比较Bruno.h和所有功能 1 请在一个文件中实施。- 不要使用标准输入/输出或文件输入/输出。
使用其他语言时
- 法官
argv[1]该值应乘以0您的程序(布鲁诺侧)以argv[1]该值应乘以1开头可以得到第 3 将执行两个程序。执行时间和内存使用量是通过它们的总和来衡量的。
安娜侧 当
argv[1]是 在0时,充当安娜一方。首先,按以下格式读取输入。
Q之后,Q 请算命。
算命
首先,按以下格式读取输入。
N接下来, 请输出
-1该值应乘以 1 行。然后执行以下操作 请重复 N 次。
- 安娜抽到的卡片上写着的数字 它在 A 是 在 1 行中给出。
- -1 \leqq x \leqq l 的整数 选择 x 该值应乘以 1 行。
最后, 包含
-1请阅读 1 行。布鲁诺侧 当
argv[1]是 在1时,充当布鲁诺的一方。首先,按以下格式读取输入。
Q之后,Q 请算命。
算命
首先,按以下格式读取输入。
N L C[0] C[1] \cdots C[L-1]之后,看算命结果。 1 行。
其他
- 每次输出后请务必冲洗。
- 当输出的格式不正确或者满足错误的答案条件时,输入的输入为
-2变为。在这种情况下,请立即终止程序。
問題文
安娜和布鲁诺热爱算命,总是一起做各种算命。今天是 0 或 1 的卡。 我决定做 Q 算命。这个算命需要两个人共同努力。1 算命的具体方法如下。 准备很多写有
- 0 或 1 的卡片,然后将它们洗入一副牌中。
- 安娜从牌堆中取出一张牌。 1 每件,总计 N (=900) 抓一张牌。安娜和布鲁诺在这里
我知道 N 的价值。安娜有一张卡片 1 每次抽一张卡,你可以选择是舍弃那张卡还是将其放置到场上并排列。
- 如果选择将它们放在场上并排列它们,请将这次要排列的卡片插入场上已排列的卡片行的所需位置。
- 具体来说,它已经就位。 如果 l 牌排列整齐,则为非负整数 x (0 \leqq x \leqq l)从场上牌行的左侧开始。 x 它可以直接插入到第二张卡的右侧。然而 x=0 插入卡片栏的最左侧位置。
- 安娜 抽完 N 卡后,安娜的角色结束。拉 N 卡片 写有 1 的卡片数量就是算命的结果。
- 最后,布鲁诺只是看着桌上摆着的一排牌,猜测算命的结果。如果布鲁诺能够正确回答算命结果,则算命成功。
在这个算命中,据说你投入的牌越少,算命的效果就越好。安娜和布鲁诺 Q 创建一个程序来实施成功算命的策略。在这个任务中,安娜投入的牌越少,你得到的分数就越高。
实施细节
你 2 您必须提交两个文件。
1 第二个文件是
名称是 Anna.cpp 。该文件实现了Anna的策略,必须实现以下功能。另外,#include 通过预处理器指令
加载 Anna.h 。
void Anna(int N)
该函数计算总计 已拨打 Q 次。 对i 回目 (1 \leqq i \leqq Q的调用是i 这对应于安娜第二次算命的程序。- 引数
N是安娜从牌堆中抽出的牌数 N 是。
功能安娜的 对于 1 调用,请使用以下函数: 必须调用 N+1 次。
int DrawCard(int x)
使用此功能从牌库中抽一张牌,并选择是否将其丢弃或放入场上。 在调用j 回目 (1 \leqq j \leqq N的返回值中,j 接收第一张抽出的牌上写的数字。k 回目 (2 \leqq k \leqq N+1)在调用的参数中 k-1 指定抽出的第一张牌的操作。 调用- j 回目 (1\leqq j \leqq N的返回值为 0 或 至少 1 安娜是 j 代表抽到的第一张牌上写的数字。
- N+1 第二次调用的返回值为 表示已抽出 -1 安娜是 N 牌。
- 1 第一次调用中的参数 x 是 您也可以写 x=-1 必须满足.如果不满足这一点 不正解 [1] 已确定。 调用
- k 回目 (2\leqq k \leqq N+1中的参数) 当 x 是 您也可以写 k-1 指定抽出的第一张牌的操作。 调用x=-1 时,k-1 丢弃抽出的第一张牌。0\leqq x时,k-1 将抽出的牌从已在玩的牌行的左侧移动。 x 表示紧邻第张卡的右侧插入。然而 x=0 表示插在卡片栏最左边的位置。在这里,我们计算已经在玩的牌的数量。 l 作为 -1 \leqq x \leqq l 。如果这还不满足,不正解 [2] 已确定。 调用
- 関数
Anna执行结束时的函数 呼叫DrawCard的次数是 如果不是 N+1 次, 名称是不正解 [3] 已确定。 调用
2 第二个文件是
名称是 Bruno.cpp 。
该文件实现了Bruno的策略并且必须实现以下功能。
另外,#include 通过预处理器指令
加载 Bruno.h 。
int Bruno(int N, int L, std::vector<int> C)
每当 Anna 完成一系列算命步骤时,此函数就会调用她。 总共 1 次 Q 次。 对i 回目 (1 \leqq i \leqq Q的调用是i 这对应于布鲁诺的第二次算命程序。安娜从甲板上划出船来。 必须返回写有 1 的卡片数量作为返回值。- 引数
N是安娜从牌堆中抽出的牌数 N 是。 - 引数
L是场上排列的牌数 L 是。 - 引数
C是长度 是一个 L 数组,C[l-1]从字段左侧开始 代表 l 番目 (1 \leqq l \leqq L中排列的卡片上写的数字。 - 関数
Bruno的返回值是安娜从牌堆中抽取的。 如果卡片数量与写入的卡片数量 1 不同,不正解 [4] 已确定。 调用
- 引数
重要说明
- 您可以自由地实现其他函数并声明全局变量以供内部使用。然而,已提交 2 这两个程序通过评分程序链接在一起。 1 因为有两个可执行文件,所以每个文件中的所有全局变量和内部函数都必须在匿名命名空间中声明,以避免与其他文件干扰。评分时,该程序将充当安娜一方和布鲁诺一方。 由于它是作为 2 进程执行的,因此程序中的全局变量不能在Anna和Bruno之间共享。
- 您提交的程序不得以任何方式与标准输入、标准输出或其他文件交互。但是,允许将调试信息等输出到标准错误输出。
如何编译执行
用于测试您创建的程序的示例评分程序包含在可从竞赛网站下载的存档中。该存档还包含必须提交的示例文件。
评分程序的示例是 1 由两个文件组成。该文件是 grader.cpp 。为了测试你的程序,
将grader.cpp,Anna.cpp,Bruno.cpp,Anna.h,Bruno.h 放在同一目录中并运行以下命令。
g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
存档中还包含
您可以改为运行文件 compile.sh 。在这种情况下,请运行以下命令。
./compile.sh
如果编译成功,
将生成一个名为grader 的可执行文件。
请注意,实际评分程序与示例评分程序不同。示例评分程序作为单个进程运行。该程序从标准输入读取输入并将结果输出到标准输出。
输入示例评分程序
示例评分程序按以下格式从标准输入读取输入。
Q N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{Q,1} A_{Q,2} \cdots A_{Q,N}
A_{i,j} (1 \leqq i \leqq Q, 1 \leqq j \leqq N) 是安娜 i 第二次算命时 j 代表抽到的第一张牌上写的数字。
评分程序的示例输出
示例评分程序将以下信息输出到标准输出(引号实际上并未输出)。
- 如果答案正确,则安娜在所有算命中投入的牌张数 L 的最大值为
Accepted: 100。 - 如果答案不正确,则错误答案的类型为
Wrong Answer [1]。
如果要执行的程序满足多个不正确的条件, 显示的错误答案类型有 1 只有一个。 如果满足错误答案条件,示例评分程序可能会中途终止执行。
评分注意事项
对于所有测试用例,实际评分程序都是自适应的。 不是 不是吗.这意味着计分程序从一开始就具有固定的从牌堆中抽牌的顺序。
制約
所有输入数据满足以下条件。
- 1 \leqq Q \leqq 100.
- N = 900.
- A_{i,j} 是 您也可以写 0 或 至少 1 (1 \leqq i \leqq Q, 1 \leqq j \leqq N).
採点基準
在此作业的测试用例中,1 总是不正解 [1] ~ [4] (参见实施细节), 如果确定超出执行时间限制、超出内存限制或运行时错误,0为点。
另外,如果您正确回答了此作业中的所有测试用例,那么在此作业中的所有测试用例中,
功能安娜的 1 调用的参数 0 \leqq x 功能 DrawCard 被调用的最大次数为 L 并将按如下方式评分。
- 500 < L 时,3 点
- 14 < L \leqq 500 时,\left\lfloor 100 \times \left(\dfrac{2.5}{L-11.5}\right)^{0.35} \right\rfloor 点
- L \leqq 14 时,100 点
交互示例
下面是示例评分程序读取的输入示例以及相应函数调用的示例。
入力例 1
2 5 0 1 0 0 1 1 1 0 1 0

这个输入示例是 Q (=2) 包括算命、2 安娜在每次算命中从牌堆中抽出的牌张数为 有 N (=5) 件。 在这个例子中,1 对于第二次算命,安娜进行如下算命。
- 安娜从牌堆中取出一张牌。 1 抓一张牌。抽到的牌上写的数字是 0 是。
- 安娜选择将抽出的牌放入游戏中并排列它们,并将它们插入到游戏中最左边的一排牌中。场上排列的牌行是 它变成 0 。安娜从牌堆中取出一张牌 1 抽一张牌,你抽到的牌上写的数字是 1 是。
- 安娜选择丢弃她抽到的牌。安娜从牌堆中取出一张牌 1 抽一张牌,你抽到的牌上写的数字是 0 是。
- 安娜选择将抽出的牌放入游戏中,并从游戏中的牌行左侧开始排列它们。 1 将其插入第二张卡的右侧。场上排列的牌行是 它变成 0,0 。安娜从牌堆中取出一张牌 1 抽一张牌,你抽到的牌上写的数字是 0 是。
- 安娜选择丢弃她抽到的牌。安娜从牌堆中取出一张牌 1 抽一张牌,你抽到的牌上写的数字是 1 是。
- 安娜选择将抽出的牌放入游戏中,并从游戏中的牌行左侧开始排列它们。 1 将其插入第二张卡的右侧。场上排列的牌行是 它变成 0,1,0 。
布鲁诺是 N 的值和字段中排列的卡片行 安娜根据 0,1,0 画了 写有 1 的卡片数量为 答案是 2 。 既然这是正确的,那么算命就成功了。安娜第一次算命时投入的牌张数 L 是 您也可以写 3 是。
2 第二次算命时安娜投入的牌张数 L 是 您也可以写 4 是。
这个输入示例是不满足约束请注意。
在可以从竞赛网站下载的文件中,sample-01-in.txt 是一个输入示例
对应于 1 。
在可以从竞赛网站下载的文件中,sample-02-in.txt 满足约束。
给出了