当前位置: 代码迷 >> 综合 >> HAUT OJ 1512: zp与草系道馆
  详细解决方案

HAUT OJ 1512: zp与草系道馆

热度:30   发布时间:2023-12-04 03:33:54.0

问题描述:

输入:

zp来到了草系道馆,馆主给了他一个另类挑战。场馆的草地长满了草,草一共n个单位zp和馆主一起清理,每个人一次可以清理1,2或3个单位的草,谁先把草清理完谁就获胜另一个就失败!两人轮流清理,并且zp先动手!(两人都是很强的,都会做出最优选择)

输出:

多实例,第一行输入T(T<10),第二行输入草的总单位数n(1<=n<=100)

样例输入:

1
5

样例输出:

zp is winner!

原因分析:

博弈论问题   公平组合游戏

巴什博弈 Bash Game

有 1 堆石子,总个数是 n ,两名玩家轮流在石子堆中拿石子,每次至少取 1 个,至多取 m 个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜。

总结:     若 n%(m+1)==0 则后手赢

情况1:当 n ≤ m 时,显然先手获胜
情况2: n = m + 1 时,先手最多可取走 m个,无论其取走多少个,剩下的后手总能一次取完。

情况3: n%(m+1)==0   则无论先手拿多少(比如x),后手总可以拿出 (m+1)-x

凑成 m+1 个,即最后一轮 同样也是剩m+1个,即情况2 ,后手赢

否则,先手可以先拿,取余后的余数,即把n%(m+1)==0的局面给后手,即先手赢
 


解决方案:

#include<stdio.h>
int main()
{scanf("%d%d", &n, &m);if (n % (m + 1))puts("zp is winner!");elseputs("curator is winner!");}