#luoguP12063. [THUPC 2025 决赛] 我的围棋

[THUPC 2025 决赛] 我的围棋

本题没有可用的提交语言。

题目描述

小 K 和小 S 在下围棋。

小 K 和小 S 在下的并不完全是围棋。

小 K 和小 S 在下的有点像围棋:一方执黑棋一方执白棋,轮流在棋盘上落子,黑方先行。如果有一片相连的棋子没有“气”了,就会被提掉。最终这些棋子由提子一方装到自己的棋盒盖里。具体来说,如果现在执黑棋的小 K 提掉了小 S 的两个白子,他必须将这两个白子装进自己的棋盒盖。

因为蒜协的棋牌室有超强的后勤供应,所以我们可以认为两人都有无限多的棋子可以下。但超强的后勤供应也会百密一疏,两人都有且仅有一个棋盒盖,而棋盒盖的大小是有限的。精通三维最密堆积的小 K 和小 S 在测算后得出,一个棋盒盖里至多能装 MM 颗棋子。

基于此,小 K 和小 S 开发出了一套船新的游戏方法,不同于中国传统围棋的排兵布阵攻守兼备,现在二人的策略都是疯狂送子,塞爆对方的棋盒盖。观战的小 Z 觉得非常有趣,于是记下了二人每一步的操作。

根据小 Z 的记载,这局棋二人一共下了 nn 手棋,其中第 ii 手棋提走了 aia_i 颗子。我们认为棋盒盖先装不下自己提走的棋子的人输掉这局棋(此时棋盒盖需要装的棋子应该严格大于 MM 颗)。如果棋盒盖溢出的情况在整局中都没有发生,则认为是平局。

现在你需要通过小 Z 的记载判断谁获得了胜利。

小 K 和小 S 都很有体育精神,因此在某人的棋盒盖被塞爆之后,他们不一定会马上结束棋局。

同时,因为这不是正经围棋,所以棋盘上的棋子可能会异常多,在棋局刚开始时也可以提走棋子。

输入格式

第一行两个整数 n (1n105)n\ (1\le n\le 10^5)M (1M109)M\ (1\le M\le 10^9),表示棋局一共下的手数和棋盒盖能装下的棋子数。

之后 nn 行每行一个整数 ai (0ai109)a_i\ (0\le a_i\le 10^9),表示第 ii 手棋提走的棋子数目。

输出格式

输出一行一个字符串表示答案。

如果最终黑方获胜,输出Black

如果最终白方获胜,输出White

如果最终平局,输出Draw

4 2
1
2
2
1

White

提示

样例 #1 解释

棋盒盖能装下 22 颗棋子。

首先黑方落子,提走 11 颗棋子,此时黑方棋盒盖里有 11 颗棋子。

第二手白方落子,提走 22 颗棋子,此时白方棋盒盖里有 22 颗棋子。

第三手黑方落子,提走 22 颗棋子,棋盒盖装不下了。所以白方获胜。

来源与致谢

来自 THUPC2025(2025 年清华大学学生程序设计竞赛暨高校邀请赛)决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public