I | Integer Game |
Two players, S and T, are playing a game where they make alternate moves. S plays first.
In this game, they start with an integer N. In each move, a player removes one digit from the integer and passes the resulting number to the other player. The game continues in this fashion until a player finds he/she has no digit to remove when that player is declared as the loser.
With this restriction, it’s obvious that if the number of digits in N is odd then S wins otherwise T wins. To make the game more interesting, we apply one additional constraint. A player can remove a particular digit if the sum of digits of the resulting number is a multiple of 3 or there are no digits left.
Suppose N = 1234. S has 4 possible moves. That is, he can remove 1, 2, 3, or 4. Of these, two of them are valid moves.
- Removal of 4 results in 123 and the sum of digits = 1 + 2 + 3 = 6; 6 is a multiple of 3.
- Removal of 1 results in 234 and the sum of digits = 2 + 3 + 4 = 9; 9 is a multiple of 3.
The other two moves are invalid.
If both players play perfectly, who wins?
Input
The first line of input is an integer T(T<60) that determines the number of test cases. Each case is a line that contains a positive integer N.N has at most 1000 digits and does not contain any zeros.
Output
For each case, output the case number starting from 1. If S wins then output ‘S’ otherwise output ‘T’.
Sample Input Output for Sample Input
3 4 33 771 | Case 1: S Case 2: T Case 3: T |
Problem Setter: Sohel Hafiz
Special Thanks: Shamim Hafiz, Md. Arifuzzaman Arif
題意:
給出一個數字串N,兩個人輪流從中取出一個數字,要求每次取完之後剩下的數之和是3的倍數(這裡之前看lrj的描述了解錯了)。不能取者輸。問先手的輸赢
如果可以,第一次取走後變為了3的倍數,則以後取的一定是3的整數倍,直至取完所有是3的整數倍的數。
是以先統計MOD 3為0 1 2的數有多少,然後先手先取一個數使得其他數之和MOD 3 = 0,不能取則輸出T
然後輪到第二個人取數了,統計MOD 3==0的數有多少,如果是偶數,則先手勝,反之先手輸。
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
//#define WIN
#ifdef WIN
typedef __int64 LL;
#define iform "%I64d"
#define oform "%I64d\n"
#define oform1 "%I64d"
#else
typedef long long LL;
#define iform "%lld"
#define oform "%lld\n"
#define oform1 "%lld"
#endif
#define S64I(a) scanf(iform, &(a))
#define P64I(a) printf(oform, (a))
#define P64I1(a) printf(oform1, (a))
#define REP(i, n) for(int (i)=0; (i)<n; (i)++)
#define REP1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FOR(i, s, t) for(int (i)=(s); (i)<=(t); (i)++)
const int INF = 0x3f3f3f3f;
const double eps = 10e-9;
const double PI = (4.0*atan(1.0));
const int maxn = 1000 + 20;
char str[maxn];
int cnt[3];
int main() {
int T;
scanf("%d", &T);
for(int kase=1; kase<=T; kase++) {
scanf("%s", str);
int n = strlen(str);
int sum = 0;
cnt[0] = cnt[1] = cnt[2] = 0;
for(int i=0; i<n; i++) {
sum += str[i] - '0';
cnt[(str[i]-'0')%3]++;
}
int t = sum % 3;
cnt[t]--;
printf("Case %d: ", kase);
if(cnt[t] < 0) {
puts("T");
continue;
}
t = cnt[0];
if(t&1) puts("T");
else puts("S");
}
return 0;
}