首页 > 其他 > 详细

【Coreforces-1194D】1-2-K Game

时间:2019-12-28 12:42:03      阅读:87      评论:0      收藏:0      [点我收藏+]

地址:https://codeforces.com/contest/1194/problem/D

题意:T组样例,给你一堆数量为a的石子,每次可以取1 ,2 或 k个,无法进行操作的人必败,输入败的人。

题解:这是一个博弈论,打表模拟, 分两种情况,

  1、如果b为3的倍数,打表模拟k = 3、6;

    当k = 3时,必败态有 0 4  8 12 ......

    当k = 6时,必败态有 0  7  14 21 .......

               3 10 17 24 .......

    结论:当 a%(k+1)%3==0并且 a%(k+1)!=k 必败。

  2、如果b不为3的倍数,不考虑取出k个(原因:只考虑必败态的话,它对必败态没有任何影响,因此必胜态也不会受到影响),也就是,只判断a%3的结果即可。

代码如下:

#include <cstdio>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(b%3==0){
            if(a%(b+1)%3==0&&a%(b+1)!=b)printf("Bob\n");
            else printf("Alice\n");
        }
        else{
            if(a%3==0)printf("Bob\n");
            else printf("Alice\n");
        }
    }
    return 0;
}

【Coreforces-1194D】1-2-K Game

原文:https://www.cnblogs.com/Vagrant-ac/p/12111170.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!