// http://uva.onlinejudge.org/external/114/11489.html
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;
int main ()
{
int testCase;
scanf ("%d", &testCase);
int cases = 0;
while ( testCase-- ) {
char num [1000 + 10];
scanf ("%s", num);
int freq [10 + 3];
memset (freq, 0, sizeof (freq));
int sum = 0;
for ( int i = 0; num [i]; i++ ) {
sum += num [i] - '0';
freq [num [i] - '0']++;
}
int allowed_move = freq [3] + freq [6] + freq [9];
printf ("Case %d: ", ++cases);
bool s_win = true;
if ( sum % 3 == 0 ) {
if ( allowed_move % 2 == 0 ) s_win = false;
}
else if ( sum % 3 == 1 ) {
if ( freq [1] || freq [4] || freq [7] ) {
if ( allowed_move % 2 ) s_win = false;
}
else s_win = false;
}
else {
if ( freq [2] || freq [5] || freq [8] ) {
if ( allowed_move % 2 ) s_win = false;
}
else s_win = false;
}
if ( s_win ) printf ("S\n");
else printf ("T\n");
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

vaia, could you please describe your logic to solve the problem? ’cause i don’t get it.

@shaon

you asked about the logic of this problem .. so i guess u know how to solve this type of game theory problems 🙂

suppose, the give number is already divisible by 3

so, to make a valid move, u have only 3 options

1. move digit 3 (if any)

2. move digit 6 (if any)

3. move digit 9 (if any)

as the number is already divisible by 3, so u can’t move other digits .. right?

if ( given number is divisible by 3 and ( freq [3] + freq [6] + freq [9] ) % 2 == 0 ) T win

else if ( given number is divisible by 3 and ( freq [3] + freq [6] + freq [9] ) % 2 == 1 ) S win

freq [3] means, number of digits 3 in the given input

……………….

if ( given number % 3 == 1 )

that means, to make a valid move, u have 3 options

1. move digit 1 (if any)

2. move digit 4 (if any)

3. move digit 7 (if any)

first move will make the resulting number divisible by 3 … and then u can apply the logic described before

……………….

same logic goes for, given number % 3 == 2

do some paper-pencil work and i hope u will get the logic 🙂

Thanks. interesting problem, and idea is more interesting.:)

but vaia, isn’t it a little observation? i mean is there anything related to game theory?

(Important to mention that) i know a little about game theory, so i want to sure about it. 😀

@shaon

i dont know game theory very well .. so i can’t assure u 😛

but every problem does need a little observation, regardless of its type and complexity .. doesn’t it? 🙂

yeah. thanks. 🙂

Looks a hard to find observation , How did you come up with it?