Skip to content

牛客网 NC205086 牛牛爱博弈#

目录#

1. 题目描述#

1.1. Title#

牛客网 NC205086 牛牛爱博弈

1.2. Time Limit#

C/C++ 1秒，其他语言2秒

1.3. Memory Limit#

C/C++ 262144K，其他语言524288K

1.4. Problem Description#

牛牛和牛妹玩博弈游戏。 牛牛：我们来玩取石子游戏。一共有n堆石子，每个人每次可以取1或2颗石子，谁取走了最后一颗石子就算谁获胜。

牛妹：这游戏太无聊了。

牛牛：那改一改。一共有n堆石子，每个人每次可以取颗石子，谁取走了最后一颗石子就算谁获胜。

牛妹：好的，你先开始取吧。

牛牛心里知道自己是否有必胜策略，但他想来考考你。

因为牛牛和牛妹很爱玩这种游戏，所以本题有多组数据。

（注：牛牛叫 ，牛妹叫 .）

1.5. Input#

第一行，输入数据组数T。

接下来T行，每行一个数n。

1.6. Output#

对于每一组数据，

如果牛牛必胜，则输出“Alan”（不含引号）；

如果牛妹胜，则输出“Frame”（不含引号）。（PS:牛牛叫 Alan ，牛妹叫 Frame ）

1.7. Sample Input 1#

3
1
2
3

1.8. Sample Output 1#

Alan
Alan
Frame

1.9. Sample Input 2#

3
17
18
19

1.10. Sample Output 2#

Alan
Frame
Alan

1.11. Note#

数据保证

1.12. Source#

牛客网 NC205086 牛牛爱博弈

2. 题解#

从直观上来说，我们很容易把输入分为 和 两种情况来讨论，如果是 则先手直接取完了所有棋子，但是 这种情况非常不好判断谁能获胜。

从输入样例1中我们可以看出，如果是 ，那么先手只能取1或者2，后手能把剩下的棋子取完，后手一定获胜。

那么，要后手必胜，则需要满足三个条件:

  1. 不能是 。
  2. 通过偶数次 运算 一定能避免 。
  3. 通过奇数次 运算 一定能减到 。

通过一些跳跃性的思维过程，我们可以想到如果 就能满足以上条件。

首先，一个数如果是3的倍数，则一定不是 ，我们可以把 的结果罗列出来，发现呈现 重复出现的规律。

其次， 时，第一次减 的运算，会让 或 ，那么在第二次减 的运算的时候，只要取 ，就能让 又成为 3 的倍数。

由此又可以推出，在先手位上出现的数字一直满足 ，并且 在不断递减，最后一定会出现 。

综上所述，只要 是 3 的倍数，后手一定获胜，输出 Frame。

反之，如果 不是 3 的倍数，先手只要取 ，把后手位上出现的数字变成 3 的倍数，则先手一定获胜，输出Alan。

3. 代码#

#include <iostream>
using namespace std;

int main(){
    int t, n, buffer;
    double sqrtBuffer;
    cin>>t;
    while(t--){
        cin>>n;
        // 是3的倍数
        if(n % 3 == 0){
            cout<<"Frame"<<endl;
        }else{
            // 不是3的倍数
            cout<<"Alan"<<endl;
        }
    }
}

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top