首页 > 代码库 > UVa 11489 整数游戏

UVa 11489 整数游戏

https://vjudge.net/problem/UVA-11489

题意:

给出一个数字串n,两个人轮流从中取出一个数字,要求每次取完之后剩下的数是3的倍数,不能取数者输。

 

思路:

要想取掉一个数后总和还是的倍数,那么取掉的数必须得是3的倍数。

分两种情况:

①数字串总和为3的倍数,此时只需要看数字串中3的倍数的个数,奇数个的话先手赢,否则后手赢。

②数字串总和不为3,那么它会余1or余2,如果余1,那么查看数字串中是否存在%3后余1的数,如果有,则转化成了①情况,否则先手就输。(同理分析余2)

 

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 10 char s[1005];11 12 int main()13 {14     int T;15     scanf("%d",&T);16     int kase=0;17     while(T--)18     {19 20         cin>>s;21         int sum=0;22         int num_0=0,num_1=0,num_2=0;23         int len=strlen(s);24         printf("Case %d: ",++kase);25         for(int i=0;i<len;i++)26         {27             if((s[i]-0)%3==0)  num_0++;28             else if((s[i]-0)%3==1)  num_1++;29             else if((s[i]-0)%3==2)  num_2++;30             sum+=s[i]-0;31         }32         if(sum%3==0)33         {34             if(num_0%2)   printf("S\n");35             else  printf("T\n");36         }37         else38         {39             if(sum%3==1)40             {41                 if(num_1 && num_0%2==0)  printf("S\n");42                 else   printf("T\n");43             }44             else if(sum%3==2)45             {46                 if(num_2 && num_0%2==0)  printf("S\n");47                 else   printf("T\n");48             }49         }50     }51     return 0;52 }

 

UVa 11489 整数游戏