51nod-1070 Bash游戏 V4

发表于 博弈 分类,标签:

 

有一堆石子共有N个。A B两个人轮流拿,A先拿。每次拿的数量最少1个,最多不超过对手上一次拿的数量的2倍(A第1次拿时要求不能全拿走)。拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛。
例如N = 3。A只能拿1颗或2颗,所以B可以拿到最后1颗石子。
Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 1000)
第2 - T + 1行:每行1个数N。(1 <= N <= 10^9)
Output
共T行,如果A获胜输出A,如果B获胜输出B。
Input示例
3
2
3
4
Output示例
B
B
A



思路:从题意可以看出,n个石子,若先拿的人拿走大于或等于n/3,另一个人课可直接拿走所有的石子,所以先拿的人肯定不能拿走超过n/3的石子,并且使剩下的石子形成先拿必败的条件。

如:

n        胜利者

1        B

2        B

3        B

4        A

5        B

6        A

7        A

8        B


当n=7时,满足小于n/3的数有1和2。若此时选择拿走2个石子,则剩下5个石子,因为当n=5时是B赢了(即先拿必败),所以7个石子取走2个后剩余5个,这时轮到B先取,无论B怎么选择,他都必输,所以当n=7时,A赢。

当n=8时,满足小于n/3的数也是1和2,此时无论取1(剩余7)还是取2(剩余6),轮到B先拿的时候A必输,所以当n=8时,B赢;

通过观察发现B赢得时候n一定是一个斐波纳契数,所以先打表出10^9内的所有斐波纳契数,再判断n是否为斐波纳契数就行。


代码:

#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include <string.h>
#define MAX 1e9
using namespace std;
int s[100];
int cut;
int main()
{
    s[1]=1;
    s[2]=2;
    cut=3;
    while(s[cut-1]<=MAX)
    {
        s[cut]=s[cut-1]+s[cut-2];
        cut++;
    }
    int t;
    int n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<45;i++)
        {
            if(s[i]==n)
            {
                printf("B\n");
                break;
            }
            else if(s[i]>n)
            {
                printf("A\n");
                break;
            }
        }
    }
    return 0;
}



0 篇评论

发表我的评论