UVa : 11489 (Integer Game)



// 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

6 thoughts on “UVa : 11489 (Integer Game)

  1. @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 🙂

  2. 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. 😀

  3. @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? 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s