← 返回题目列表

Codeforces · 1033/G

G. 筹码游戏

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

Alice 和 Bob 决定玩一场终极游戏。他们有 $$$n$$$ 堆,第 $$$i$$$ 堆最初包含 $$$v_i$$$ 筹码。 Alice从区间$$$[1, m]$$$中选择一个正整数$$$a$$$,Bob以同样的方式选择一个数字$$$b$$$。

然后游戏开始。轮到 Alice 时,她可以选择任何至少包含 $$$a$$$ 筹码的堆,并从中准确删除 $$$a$$$ 筹码。同样,轮到鲍勃可以选择任何至少有 $$$b$$$ 筹码的堆,并从中恰好移除 $$$b$$$ 筹码。如果玩家无法采取行动,他或她就输了。

如果两名玩家都发挥最佳,结果最终取决于 $$$a$$$ 和 $$$b$$$ 的选择以及起始玩家。考虑一个固定对 $$$(a,b)$$$。游戏有四种类型:

- 无论谁开始,爱丽丝都会获胜。
- 无论谁先发,鲍勃都会获胜。
- 如果爱丽丝开始,她就赢了。如果鲍勃开始,他就赢了。我们说第一个玩家获胜。
- 如果爱丽丝开始,鲍勃获胜。如果鲍勃开始,爱丽丝就赢了。我们说第二个玩家获胜。

在 $$$a$$$ 和 $$$b$$$ 的所有选择中(即对于每对 $$$(a, b)$$$ 使得 $$$1\leq a, b\leq m$$$),确定 Alice 赢得了多少场比赛(无论谁开始),Bob 赢得了多少场(无论谁开始),第一个玩家赢得了多少场,以及第二个玩家。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 10^5$$$) — 分别是桩数和一回合允许获取的筹码数量上限。

第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$1 \leq v_i \leq 10^{18}$$$) — 每堆筹码的起始数量。

输出

打印一行,其中包含四个整数 $$$w_a$$$、$$$w_b$$$、$$$w_f$$$、$$$w_s$$$ - 分别是 Alice、Bob、第一个玩家和第二个玩家赢得的游戏数量。

示例

输入 #1

2 2
4 5

输出 #1

1 1 1 1

输入 #2

2 20
4 5

输出 #2

82 82 6 230

注意

在第一个示例中,元组 $$$(a,b)$$$ 共有四个选择。

- $$$a = b = 1$$$:从哪堆筹码中取出并不重要 - 总共有 $$$9$$$ 轮,第一个玩家也轮到了最后一个,因此他获胜。
- $$$a = b = 2$$$:第二个玩家可以通过始终选择与第一个玩家相同的筹码堆来获胜,然后筹码堆中有 $$$0$$$ 和 $$$1$$$ 筹码。由于不可能从其中任何一个中取出 $$$2$$$ 筹码,因此第一个玩家就输了。
- $$$a = 1$$$ 和 $$$b = 2$$$:假设 Alice 开始。她可以通过从筹码 $$$5$$$ 的筹码堆中取出一个筹码,然后复制鲍勃的决定来获胜。在接下来的四轮之后,游戏结束,每堆筹码为 $$$1$$$,而鲍勃无法采取行动。 假设鲍勃开始。如果他从第二堆中取出两个筹码,爱丽丝就会从第一堆中取出一个筹码来反击。从那时起,她总是可以复制鲍勃的决定并获胜。如果鲍勃在第一回合中从第一堆筹码中取出两个筹码,那么爱丽丝也可以取出一个。由于第一堆筹码只剩下一个,鲍勃被迫从第二堆筹码中取出两个筹码,留下$$$3$$$。无论爱丽丝做什么,她都会赢。 因此,无论谁先开始,爱丽丝都会获胜。
- $$$a = 2$$$ 和 $$$b = 1$$$:这与之前的情况对称 - 因此鲍勃总是获胜。

在第二个示例中,很多游戏,例如$$$a = 7$$$ 和 $$$b = 6$$$,最终没有人能够移除单个筹码——这算作第二位玩家的胜利。第一个玩家赢得的游戏为 $$$(1, 1)$$$、$$$(1, 4)$$$、$$$(2, 3)$$$、$$$(3, 2)$$$、$$$(4, 1)$$$ 和 $$$(5, 5)$$$。