题目描述:
期末考试就要来临了,大家都在紧张的复习。作为在考场拼搏了十几载的当代大学生,小明和小华更懂得考前的放松。他们在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
他们打牌的规则是这样的:
总共 n 张牌;
双方轮流抓牌;
每人每次抓牌的个数只能是 2 的幂次,即 1,2,4,8,16 等。
抓完牌,胜负结果也出来了,最后抓完牌的人为胜者;
假设小明和小华都足够聪明,并且每次都是小明先抓牌,请问谁能赢呢?
输入输出格式
输入格式
输入包含一个整数 n,表示扑克牌的数量。
输出格式
针对输入,如果小明能赢的话,请输出 ming,否则请输出 hua。
输入输出样例1
输入
1
输出
ming
输入输出样例2
输入
3
输出
hua
说明提示
1≤n≤1000
思路解析:
这道题看似很复杂,实际上和上一篇文章(老虎与羊)有类似的感觉。同样的咱们先进行假设。
假设我是小明,那么在只有一张牌的情况下我会怎么做呢?我当然要只抓一张直接绝杀小华。
如果有两张牌呢?当然直接抓两张结束游戏。
如果有三张呢?我发现我无论是抓一张还是两张都会剩下牌,结果也就是剩一张或者两张,现在轮到小华抓牌了,这时候他可以全抓走结束游戏。
假如有四张呢?我可以直接结束游戏。
5张呢?关键的来了,如果是轮我先抓牌,仅剩3张牌对我来说是个“炸弹”,那么我们不妨将“炸弹”送给对面。如果有5张,我只拿2张,让小华面临先抽牌,场上只有3张牌的情况,小华必输。
我们发现了规律,只要找到会形成炸弹的局面然后送给对面就能赢,因为“炸弹”是相对的,对于我们来说,先抽牌并且场上只有三张牌我们一定会输,对面也一样,对于我们来说必胜的局面,比如5张牌先抽给对面一样也是必胜。
假设场上有6张牌,我发现从1~5中“炸弹”只有3,我无论怎么抽都不能把炸弹送给他,既然对我来说1~5除了3,都是必胜局,对于小华也一样必胜,所以这局小华必胜。
假设场上有7张牌呢?1~6中必输局是只有3张或者6张,我可以抽一张将必输局送给小华。
8张我会抽2张。
9张无法凑出必输局。
总结我们发现n是3的倍数小华会输,否则回应。
具体代码:
#include<stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
if (n % 3)
printf("ming");
else
printf("hua");
return 0;
}