当前位置：首页 > 编程日记 > 正文

【ACM】熊孩子的乐趣

编程日记 2024-10-17 05:40:00

题目链接：http://acm.nuc.edu.cn/OJ/contest/show/43/1000

【问题描述】

Alice跟Bob是学校里出了名的两个熊孩子，会在任何事情上争个高低，彼此都不服输。幼儿园的老师每次分糖果的时候看到这两个熊孩子也很头疼，两个人都想占便宜，争个你胜我负，老师还要想办法来安慰输了的一方。

老师每次会拿n个糖果来分给Alice跟Bob，老师规定了每人每次最多只能在盘子里拿走m个糖果（小朋友每次至少都要拿一个），由于Alice是女孩子，所以每次由Alice先从盘子里拿，然后是Bob。Alice跟Bob数学不好，他们并不知道拿的多的人是占便宜的一方，他们认为拿走最后一个糖果的人是胜利者，这样可以扮鬼脸来嘲对方。

老师这可发愁了，他不知道每天分糖果的时候Alice跟Bob谁胜谁负，总得有个准备去安慰下哭鼻子的那个。老师希望你可以帮帮他，提前算出每次分糖果谁会赢。（假设Alice跟Bob每次决定拿走糖果数量的目的都是为了让自己可以成功拿走最后一个，成为最后的赢家）。

【输入描述】

第一行输入一个T，表示有T组测试数据。

对于每组测试数据，包含两个正整数n，m。(1<=n,m<=1000000000)

【输出描述】

先手：Alice

后手：Bob

输出一行 Alice OR Bob

巴什博弈

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

所以在本题中，只要 n%(m+1)==0，那么一定是后者胜利

#include <stdio.h>
int main ()
{int T,n,m;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);if(n%(m+1)!=0)	printf("Alice\n");else	printf("Bob\n");}return 0;
}

https://www.dkcj.cn/info/23395.html

【ACM】熊孩子的乐趣

巴什博弈

相关文章：

mysql insertOrUpdate 方法

软件破解工具整理收集

Linux 下 UltraEdit 版本： 16.1.0.18 破解 30 天试用限制

【ACM】杭电OJ 2149

PV UV IP

VBA中级班课时3小结

解决firefox ubuntu无法打开页面的问题

js构造函数式编程

【ACM】绝地求生

【oracle】dblink创建

ASan(Linux)，gcc4.8以上版本自带的内存检查工具

详解使用DockerHub官方的mysql镜像生成容器

【ACM】奇怪的回文数

java I/O之装饰者模式

ubuntu下wireshark添加root权限

Oracle导出空表解决办法

【ACM】图像分类

【译】如何精确判断最终用户响应时间过长的原因？

javascript中重要概念-闭包-深入理解

ssl握手过程和ca证书验证

【ACM】练武奇才

Bat命令学习

记一次CentOS7内核kernel的删除重装

tcpdump抓包并保存到远程服务器

【ACM】家喻户晓的中药店（待更）

常用MySQL的命令集锦

google的gn构建系统

【ACM】五子棋

源码编译安装httpd及其常见错误

Nhibernate3循序渐进(三): 一对多映射和级联保存