首页 > 试题广场 >

博弈

[编程题]博弈

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

XHRlyb在和Cwbc玩游戏。
在一个多重集合中有在[l,r]中的全部整数各一个，即l，l+1，l+2，......，r。
每次XHRlyb和Cwbc可以选择一个大于0的数字p，把p从多重集合中删去，然后向集合中加入k个 $\lfloor \frac{p}{k} \rfloor$ ，最后不能操作的人算输。

如果博弈双方都是绝顶聪明的，并且XHRlyb先手，请你来帮XHRlyb预测这一局游戏谁会获胜。

如果博弈双方谁也无法取胜，那么判定为平局。

聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

输入描述:

输入数据有多行，每行有三个正整数，l，r，k。

输出描述:

输出数据应有多行，如果这一局XHRlyb获胜，那么请输出XHRlyb；如果Cwbc获胜，请输出Cwbc；如果两人平局，请输出Draw。

示例1

输入

1 3 2

输出

XHRlyb

示例2

输入

1 4 2

输出

Cwbc

备注:

1 ≤ l ≤ r ≤ 10⁵。
1 ≤ k ≤ 100。
1 ≤ 数据组数 ≤ 1000。

算法知识视频讲解

大桔骑士v

发表于 2019-09-15 19:06:56

1 分析胜负仅当时候，会陷入无限循环，两者会平手。当大于时候，每个数字总是会变成个向下取整，然后再以此规则变化。两人每次选择哪个数字其实没有影响，就看一共要消除多少次，才能让这里所有的数字都变成0。显然，这和数字的大小有关系，当在到的范围内，每个数字要消除1次。当在到的范围内，每个数字要消除展开全文

小琢卷不动

发表于 2021-11-23 16:15:19

其实这个游戏跟双方是否“绝顶聪明”无关，因为方案都是唯一的，只需要判断一下到底谁会赢就好了。考虑分类讨论，类似整除分块的思路：每个数变成 kkk 个 ⌊nk⌋\lfloor\dfrac{n}{k}\rfloor⌊kn⌋ 当 n∈[k0,k1−1]n \in [k ^ 0, k ^ 1 - 1 展开全文