AT_xmascon24_g.Game Pack
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
黑兔和白兔正在进行一场游戏。这场游戏的状态可以描述为“有若干个碟子排成一列,每个碟子上放有若干颗糖果”。
本游戏由给定的整数 A∈{0,1,2,3,4},B∈{0,1,2},C∈{0,1},D∈{0,1} 来确定规则,具体如下所述。
- A 用于操作的规定。操作指对某一个碟子进行变更。
- B 用于行动的规定。行动指对若干个碟子同时进行操作。黑兔先手、白兔后手,二人交替行动。
- C 用于结束的规定,表示游戏结束的条件。
- D 用于胜负的规定,即游戏结束时黑兔和白兔胜负的判断。
有 T 个游戏初始状态给出。每个初始状态由碟子的数量 N 以及每个碟子上糖果数量 X1,X2,…,XN 给出。请你对于每个初始状态,独立判断是黑兔还是白兔有必胜策略。
操作
对每个放有 x 颗糖果的碟子,操作方式如下。无论何种情况,不能取超过当前碟子糖果数的糖果,吃掉的糖果会消失。
- 当 A=0 时,取走并吃掉至少 1 颗糖果。
- 当 A=1 时,取走并吃掉至少 1、至多 3 颗糖果。
- 当 A=2 时,取走并吃掉至少 1、至多 ⌊21x⌋ 颗糖果。
- 当 A=3 时,
- 若 x 是 17 的倍数,必须正好取走 1 颗糖果。
- 若 x 不是 17 的倍数,取走并吃掉至少 1 颗、至多 2 颗糖果。
- 当 A=4 时,取走并吃掉至少 1 颗、至多 x−1 颗糖果,并新加一个碟子,把取走的糖果放到新碟子上(碟子的数量会增加)。
行动
行动方式如下。
- 当 B=0 时,选择恰好一个碟子进行一次操作(不能选择没有可操作的碟子)。
- 当 B=1 时,选择至少一个碟子,对每个所选碟子分别进行一次操作(不能选择没有可操作的碟子)。
- 当 B=2 时,选择所有可进行操作的碟子,对每个进行一次操作(没有可操作的碟子则忽略)。
结束
游戏结束条件如下。
- 当 C=0 时,当所有碟子均无可进行的操作时,游戏结束。
- 当 C=1 时,只要有任意一个碟子无法进行操作,游戏即结束。
胜负
当游戏结束时,依据下一位该行动的人(也就是本应接下来行动的人)来判断胜负:
- 当 D=0 时,下一位行动的人为败方,对方为胜方。
- 当 D=1 时,下一位行动的人为胜方,对方为败方。
输入格式
标准输入的第 1 行,依次给出 A,B,C,D,T,格式如下:
A B C D T
接下来 T 个初始状态,每个输入格式如下:
N X1 X2 ⋯ XN
输出格式
对于每个初始状态,按顺序各输出一行。若黑兔有必胜策略,输出 Black;若白兔有必胜策略,输出 White。
输入输出样例
输入#1
2 0 0 0 2 2 5 6 3 6 10 12
输出#1
Black White
输入#2
3 1 1 0 2 3 15 15 20 2 1 17
输出#2
White Black
输入#3
4 2 0 1 3 1 1 1 2 3 7 11 9
输出#3
Black White White
说明/提示
部分得分
- 对于所有满足 a∈{0,1,2,3,4},b∈{0,1,2},c∈{0,1},d∈{0,1} 的组,每当你在 (A,B,C,D)=(a,b,c,d) 的数据集上答对,分别可获得 d+1 分。数据集名中,
Set后的 4 个数字依次代表 a,b,c,d。 - 在无额外限制的数据集上答对,额外可获得 10 分,数据集名为
All。
样例解释 1
考虑第 1 个初始状态。将输入顺序的碟子分别称为碟子 1,2。黑兔的第一个回合中可以进行的行动有如下 5 种:
- 从碟子 1 取走 1 颗糖果。
- 从碟子 1 取走 2 颗糖果。
- 从碟子 2 取走 1 颗糖果。
- 从碟子 2 取走 2 颗糖果。
- 从碟子 2 取走 3 颗糖果。
可证明,黑兔存在第一个回合选择“从碟子 2 取 1 颗糖果”的必胜方案。
样例解释 2
考虑第 2 个初始状态。将输入顺序的碟子分别称为碟子 1,2。黑兔的第一个回合中可以进行的行动有如下 3 种:
- 从碟子 1 取 1 颗糖果。
- 从碟子 2 取 1 颗糖果。
- 同时从碟子 1、2 各取 1 颗糖果。
当黑兔执行“同时从碟子 1 和 2 各取 1 颗糖果”这一行动后,碟子 1 剩 0 颗、碟子 2 剩 16 颗糖果。此时,碟子 1 已无可进行的操作,游戏结束,黑兔获胜。
样例解释 3
对于第 1 个初始状态,唯一的碟子无法进行操作,游戏初始即结束,黑兔获胜。
对于第 2 个初始状态,仅能进行的行动是“从唯一的碟子取 1 颗糖果,并新加一个碟子放上去”。黑兔行动后,两个碟子都无法操作,游戏结束,白兔获胜。
对于第 3 个初始状态,按输入顺序称为碟子 1,2,3。可以考虑这样的一回合操作:“同时从碟子 1,2,3 分别取 1,10,4 颗糖果,新加碟子 1′,2′,3′ 分别各放 1,10,4 颗”。黑兔行动后,白兔回合时,有碟子 1,1′,2,2′,3,3′,各自糖果为 6,1,1,10,5,4。此时白兔将在碟子 1,2′,3,3′ 行动。
数据范围
- A∈{0,1,2,3,4}。
- B∈{0,1,2}。
- C∈{0,1}。
- D∈{0,1}。
- 1≤T≤104。
- 对于每个初始状态,1≤N≤50。
- 对于每个初始状态,1≤Xi≤5×105(1≤i≤N)。
由 ChatGPT 5 翻译
输入解题思路,AI测评打分。不知道怎么写?