博弈论 -- 巴什博弈

参考文献：

https://wiki.mbalib.com/wiki/%E5%8D%9A%E5%BC%88%E8%AE%BA

《博弈策略》

前言：

　　什么是博弈论？古语有云，世事如棋。生活中每个人如同棋手，其每一个行为如同在一张看不见的棋盘上布一个子，精明慎重的棋手们相互揣摩、相互牵制，人人争赢，下出诸多精彩纷呈、变化多端的棋局。博弈论是研究棋手们 “出棋” 着数中理性化、逻辑化的部分，并将其系统化为一门科学。换句话说，就是研究个体如何在错综复杂的相互影响中得出最合理的策略。事实上，博弈论正是衍生于古老的游戏或曰博弈如象棋、扑克等。数学家们将具体的问题抽象化，通过建立自完备的逻辑框架、体系研究其规律及变化。这可不是件容易的事情，以最简单的二人对弈为例，稍想一下便知此中大有玄妙：若假设双方都精确地记得自己和对手的每一步棋且都是最“理性” 的棋手，甲出子的时候，为了赢棋，得仔细考虑乙的想法，而乙出子时也得考虑甲的想法，所以甲还得想到乙在想他的想法，乙当然也知道甲想到了他在想甲的想法…

　　面对如许重重迷雾，博弈论怎样着手分析解决问题，怎样对作为现实归纳的抽象数学问题求出最优解、从而为在理论上指导实践提供可能性呢？

　　通过博弈论的学习，希望也能够提升自己解决问题的能力和决策力，博弈论是一门很深的学问，也不是看几本书就能够掌握的，正所谓高山仰止，也希望能汲取一丝的知识也算是心满意足，更多的是对这门学问的好奇

　　那么这次学习主要针对博弈算法来展开学习的，针对不同的博弈算法找出最优解

今天用一个赛题来开始我们的博弈之旅行：

巴什博弈

巴什博弈（定理献上）：

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

n = (m+1)r+s , (r为任意自然数,s≤m), 即n%(m+1) != 0, 则先取者肯定获胜。

巴什博弈还是很好理解滴，以你是先手的角度考虑。你想把对手给弄垮，那么每一局，你都必须构建一个局势，这个局势就是每次都留给对手m+1的倍数个物品（为什么留给m+1倍就一定能赢，你稍微动动脑子就出来了）。所以不只是取物品中的博弈可以用到巴什定理，还可以是报数之类的，看谁先报到100.并且每次报的数必须是1~10（包括1跟10），那么你每次都应该留给对手剩下的报数个数为11的倍数。

Problem Description

大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”？“双扣”？“红五”？还是“斗地主”？
当然都不是！那多俗啊~
作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：
1、  总共n张牌;
2、  双方轮流抓牌；
3、  每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、  抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢？
当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。

Good luck in CET-4 everybody!

Input
输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n（1<=n<=1000）

Output
如果Kiki能赢的话，请输出“Kiki”，否则请输出“Cici”，每个实例的输出占一行。

Sample Input

1
3

Sample Output

Kiki
Cici

分析：

如果你是先手，那么请考虑你的必胜点。由于规定只能去2的幂次，那么只要你留给对手的牌数为3的倍数时，那么你就必赢，因为留下3的倍数时，对手有两种情况：1，要么取剩下1，给你胜利 2，要么对手取了一点点儿，轮到你时，你就又可以构造一个3的倍数了嘛。所以无论哪种情况，当你留给对手为3N的时候，你是必胜的。好吧，题目说你就是Kiki,那么当牌数为3的倍数时，Kiki就输了。因为一出来，上帝就留给了Kiki一个3的倍数。没办法，但是如果一开始上帝留给Kiki的不是3的倍数，那么Kiki肯定能够用先手的优势构造出3的倍数，那么Kiki就必胜。所以代码是异常的简单啊

#include <stdio.h>
#include <stdlib.h>

int main(void) 
{ 
    int n = 0; 
    while(scanf("%d",&n)==1) 
    { 
        if(n%3==0) 
            printf("Cici"); 
        else 
            printf"Kiki"); 
   } 
}