2015年2月5日 星期四

2015/02/05 ACM-ICPC Live Archive 3668 - A Funny Stone Game (UVA 1378)

/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1669 */
#include <iostream>
#include <cstdio>

using namespace std;

bool hv[1000];
int gdy[50];
int v[50];

int N;

int process()
{
    int Ans = 0;

    for(int Ni = 0; Ni < N; Ni++)
    {
        if( v[Ni]%2 == 1 )
            Ans ^= gdy[N-Ni-1];
    }

    return Ans;
}

int main()
{
    for(int i = 0; i <= 30; i++)
    {
        fill(hv, hv+1000, false);

        for(int j = 0; j < i; j++)
            for(int k = 0; k < i; k++)
            {
                int p = gdy[j]^gdy[k];

                if( p < 1000 )
                    hv[p] = true;
            }

        for(int j = 0; j < 1000; j++)
            if( !hv[j] )
            {
                gdy[i] = j;
                break;
            }
    }

    int cnt = 0;

    while( scanf("%d", &N) != EOF )
    {
        if( !N ) break;

        ++cnt;

        for(int Ni = 0; Ni < N; Ni++)
            scanf("%d", &v[Ni]);


        printf("Game %d:", cnt);

        bool OK = false;

        for(int Ni = 0; !OK && Ni < N; Ni++)
            for(int Nj = Ni+1; !OK && Nj < N; Nj++)
                for(int Nk = Ni+1; !OK && Nk < N; Nk++)
                {
                    if( v[Ni] )
                    {
                        v[Ni]--;
                        v[Nj]++;
                        v[Nk]++;

                        if( !process() )
                        {
                            OK = true;
                            printf(" %d %d %d\n", Ni, Nj, Nk);
                        }

                        v[Ni]++;
                        v[Nj]--;
                        v[Nk]--;
                    }
                }

        if( !OK ) puts(" -1 -1 -1");
    }
}

沒有留言:

張貼留言