← 返回题目列表

Codeforces · 1312/F

F. 对红色王国的攻击

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

红王国遭到白王和黑王的攻击!

王国由$$$n$$$个城堡守卫,第$$$i$$$个城堡由$$$a_i$$$士兵守卫。为了征服红色王国,国王们必须消灭所有的守军。

白王每天都会对其中一座城堡发动攻击。然后,到了晚上,黑王的军队袭击了一座城堡(可能是同一座城堡)。然后白王攻击城堡,然后是黑王,依此类推。第一次攻击是由白王发起的。

每次攻击必须针对一座城堡,其中至少有一名活着的防御者。攻击分为三种类型:

- 混合攻击使目标城堡中的防御者数量减少$$$x$$$(如果防御者数量已经少于$$$x$$$,则将其设置为$$$0$$$);
- 步兵攻击会使目标城堡中的防御者数量减少$$$y$$$(如果防御者数量已经少于$$$y$$$,则将其设置为$$$0$$$);
- 骑兵攻击会使目标城堡中的防御者数量减少$$$z$$$(如果防御者数量已经少于$$$z$$$,则将其设置为$$$0$$$)。

混合攻击可以对任何有效目标(任何至少有一名士兵的城堡)发起。但是,如果之前对目标城堡的攻击具有相同类型,则无论何时、由何人发起,都无法发起步兵攻击。骑兵进攻也是如此。根本没有受到攻击的城堡可以成为任何类型的攻击的目标。

发动最后一次攻击的国王将被尊为红色王国的征服者,因此两位国王都想发动最后一次攻击(他们足够聪明,找到了一种策略,无论对手的行动是什么,都可以让他们这样做,如果这种策略存在的话)。白王正在领导他的第一次进攻,你负责策划它。你能计算出让白王发动最后一次攻击的第一次攻击有多少种可能的选择吗?第一次攻击的每个选项由目标城堡和攻击类型来表示,如果目标城堡或攻击类型不同,则两个选项不同。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是测试用例。每个测试用例由两行表示。

第一行包含四个整数 $$$n$$$、$$$x$$$、$$$y$$$ 和 $$$z$$$ ($$$1 \le n \le 3 \cdot 10^5$$$、$$$1 \le x, y, z \le 5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^{18}$$$)。

保证输入中所有测试用例的 $$$n$$$ 值之和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印答案:白王第一次攻击的可能选项数量(或 $$$0$$$,如果无论白王如何行动,黑王都可以发起最后一次攻击)。

示例

输入 #1

3
2 1 3 4
7 6
1 1 2 3
1
1 1 2 2
3

输出 #1

2
3
0

输入 #2

10
6 5 4 5
2 3 2 3 1 3
1 5 2 3
10
4 4 2 3
8 10 8 5
2 2 1 4
8 5
3 5 3 5
9 2 10
4 5 5 5
2 10 4 2
2 3 1 4
1 10
3 1 5 3
9 8 7
2 5 4 5
8 8
3 5 1 4
5 5 10

输出 #2

0
2
1
2
5
12
5
0
0
2