Give me some tests.
Some my tests
Input:
3
9 2 1 3 1 4 1 1 1 5
3 1 2 1
3 1 2 1
Output:
G
1 2
Input:
1
5 2 3 1 4 5
Output:
G
1 3
Input:
1
5 5 4 1 3 2
Output:
G
1 1

Edited by author 25.09.2007 20:24

Could you give me some tests to train my code? I WA in test 6 many times and I don't know why anymore.. I need some people to help me.
Here is my code:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int sg[55][110][110];
int a[110][110];
int n;
bool v[110], l[110];
int mex ( int l, int r, int x ){
    if ( sg[x][l][r] != -1 ) return sg[x][l][r];
    if ( l > r ) return 0;
    int i, j, k;
    int p, ss;
    memset ( v, false, sizeof (v) );
    for ( i = l; i <= r; i ++ ){
        p = a[x][i]; ss = 0;
        k = l;
        for ( j = l; j <= r; j ++ ){
            if ( a[x][j] <= p ){
                ss ^= mex ( k, j-1, x );
                k = j+1;
            }
        }
        ss ^= mex ( k, r, x );
        v[ss] = true;
    }
    for ( i = 0; ; i ++ ){
        if ( v[i] == false ){
            sg[x][l][r] = i;
            return i;
        }
    }
}
int get_sg ( int x ){
    int i, j, k;
    for ( i = 1; i <= a[x][0]; i ++ ) sg[x][i][i] = 1;
    return mex ( 1, a[x][0], x );
}
void get_way ( int ans ){
    int i, j, k, x, y, o;
    int p, s;
    for ( i = 1; i <= n; i ++ ){
        for ( j = 1; j <= a[i][0]; j ++ ){
            p = a[i][j]; s = 0;
            o = 1;
            for ( k = 1; k <= a[i][0]; k ++ ){
                if ( a[i][k] <= p ){
                    s ^= mex ( o, k-1, i );
                    o = k+1;
                }
            }
            s ^= mex ( o, a[i][0], i );
            if ( (ans^sg[i][1][a[i][0]]^s) == 0 ){
                printf ( "%d %d\n", i, j );
                return;
            }
        }
    }
}
int main (){
    int i, j, k;
    scanf ( "%d", &n );
    k = 0;
    memset ( sg, -1, sizeof (sg) );
    for ( i = 1; i <= n; i ++ ){
        scanf ( "%d", &a[i][0] );
        for ( j = 1; j <= a[i][0]; j ++ ) scanf ( "%d", &a[i][j] );
        get_sg (i);
        k ^= sg[i][1][a[i][0]];
    }
    if ( k == 0 ) printf ( "S\n" );
    else{
        printf ( "G\n" );
        get_way (k);
    }
    return 0;
}

The following test helped me:

Input:
17
84 47 44 99 60 43 14 91 8 39 26 15 41 70 90 41 72 48 20 59 3 68 15 21 78 95 5 22 60 61 88 43 59 84 94 19 26 7 61 85 97 86 51 89 55 40 29 78 39 100 89 41 19 3 62 97 98 18 70 9 79 57 51 37 92 96 55 17 55 67 54 3 52 4 92 59 44 20 36 34 72 24 27 90 79
88 38 28 57 7 36 35 16 38 24 7 34 30 76 88 97 29 90 100 32 33 58 27 5 46 61 76 69 87 65 99 26 3 26 34 61 13 69 76 51 92 83 36 73 10 23 69 38 64 69 21 49 78 100 53 23 12 28 92 50 44 42 27 98 20 60 59 32 28 34 82 71 68 17 96 77 91 64 66 7 84 87 55 62 86 59 84 49 86
27 98 29 69 24 27 88 83 37 19 63 22 53 85 90 21 80 18 64 44 84 70 79 22 76 40 59 34
24 7 71 2 4 51 70 27 29 9 61 65 80 23 87 84 8 28 4 87 45 67 82 80 88
61 53 15 100 11 100 75 69 70 77 24 73 98 50 1 59 63 18 38 85 4 73 92 83 76 31 79 95 64 59 34 24 63 49 76 26 100 2 94 70 30 18 42 80 19 94 38 81 11 27 18 14 99 61 48 26 91 27 72 55 37 6
30 99 6 57 24 5 11 18 26 92 87 19 71 57 13 60 38 23 38 55 89 88 15 36 66 58 62 37 64 98 42
45 97 99 54 72 56 64 41 81 55 27 100 78 36 64 37 73 86 27 79 26 14 45 62 79 54 75 16 17 25 9 62 73 60 67 44 15 30 85 47 36 63 98 13 50 61
2 22 99
28 52 24 93 49 37 72 2 12 39 19 36 99 32 8 10 98 3 24 79 39 23 14 54 20 27 3 81 80
77 79 7 80 2 99 28 39 22 30 2 12 100 89 11 31 48 20 80 50 96 58 41 18 23 94 37 1 48 69 80 76 47 38 56 1 89 83 91 10 12 44 22 11 32 84 93 79 55 24 80 50 81 20 19 4 65 56 56 65 76 36 40 75 73 95 75 61 30 17 23 93 60 44 56 43 79 48
73 33 72 52 35 4 24 53 59 40 60 15 4 36 2 96 10 74 42 36 87 71 4 9 64 15 4 19 57 34 18 29 66 41 32 52 45 55 5 55 47 16 69 50 3 70 97 64 96 39 99 34 9 54 42 24 68 97 94 24 30 12 4 47 4 36 99 48 90 55 55 36 70 75
38 25 45 86 88 92 24 39 25 85 92 18 60 60 66 54 35 47 17 39 93 20 26 43 20 15 49 74 3 71 48 92 95 44 29 82 35 53 20
11 89 12 80 48 23 45 53 57 91 69 47
36 89 72 30 8 39 79 33 93 49 80 36 95 24 64 76 10 68 96 73 56 59 52 56 81 49 8 89 91 29 88 78 17 59 8 76 49
38 8 41 38 39 76 32 62 40 7 24 59 54 96 15 12 47 22 44 47 81 85 38 9 72 15 77 30 22 4 79 11 63 71 48 2 99 79 15
90 38 38 48 43 33 62 7 32 35 50 78 16 86 67 76 57 82 5 39 55 8 17 66 71 39 65 72 37 96 86 26 33 76 74 27 8 87 33 91 74 35 21 89 20 87 16 77 68 20 15 23 28 83 40 50 73 4 73 10 99 58 87 83 85 60 10 93 99 94 35 72 28 55 12 48 42 27 76 61 99 42 35 78 24 74 27 96 30 99 57
80 8 44 15 93 55 24 37 53 17 71 76 97 78 39 96 71 18 71 31 16 12 66 93 87 91 71 34 72 69 91 52 76 86 66 20 40 41 56 45 9 79 72 5 56 11 100 26 80 70 8 47 33 73 39 71 16 9 5 87 29 47 38 56 84 55 76 23 95 31 19 4 61 43 8 68 5 60 93 84 29

Output:
G
1 67

If you have WA 13, try this test:

3
1 1
1 1
1 1

It may help you.

What is this test? I cannot find my mistake.

Hi, I'm using grundy numbers for this problems, however I get WA 5.

#include <cstdio>
#include <cstring>

using namespace std;

int n[50],a[50][100];
int g[50][100][100];

int main(){
    int K;

    scanf("%d",&K);

    for(int i = 0;i < K;++i){
        scanf("%d",&n[i]);

        for(int j = 0;j < n[i];++j)
            scanf("%d",&a[i][j]);
    }

    memset(g,0,sizeof g);

    bool have[201];

    for(int k = 0;k < K;++k){
        for(int l = 1;l <= n[k];++l){
            for(int i = 0;i + l <= n[k];++i){
                memset(have,false,sizeof have);

                for(int j = i;j < i + l;++j){
                    int x = a[k][j],sum = 0;

                    for(int s = i;s < i + l;){
                        if(a[k][s] <= x) ++s;
                        else{
                            int e = s;

                            while(e < i + l && a[k][e] > x) ++e;

                            sum ^= g[k][s][e - 1];
                            s = e + 1;
                        }
                    }

                    have[sum] = true;
                }

                while(have[ g[k][i][i + l - 1] ])
                    ++g[k][i][i + l - 1];
            }
        }
    }

    int G = 0;

    for(int k = 0;k < K;++k)
        G ^= g[k][0][n[k] - 1];

    if(G){
        puts("G");

        bool found = false;

        for(int k = 0;k < K && !found;++k){
            for(int i = 0;i < n[k] && !found;++i){
                G = 0;

                for(int j = 0;j < K;++j)
                    if(j != k)
                        G ^= g[k][0][n[j] - 1];

                int x = a[k][i],sum = 0;

                for(int s = 0;s < n[k];){
                    if(a[k][s] <= x) ++s;
                    else{
                        int e = s;

                        while(e < n[k] && a[k][e] > x) ++e;

                        G ^= g[k][s][e - 1];
                        s = e + 1;
                    }
                }

                if(G == 0){
                    found = true;
                    printf("%d %d\n",k + 1,i + 1);
                }
            }
        }
    }else puts("S");



    return 0;
}

I mean, why is it Batlle instead of Battle?

After trying to solve this most-likely-not-the-hardest-one problem for more than a week I started doubting in my understanding of its statement.

The question is: what does it mean "remaining chains"? Are players enforced to finish up some chain before touching others (and so recursively) or are they allowed to pick ANY chain after breaking up some other?

I.e. what is the answer for the following test:

2
2 1 2
2 1 2

Is it

G
1 1

or is it

S

?

If Gandalf converts chain -1-2- into chain -2- by dematiarilizing ring 1, is Sauron allowed to pick some ring in the other -1-2- chain or is he enforced finish off that -2- remnant of the first chain before getting hands onto the 2nd one?

And what is the answer to this test?

3
3 1 2 3
2 1 2
1 1

Edited by author 21.09.2008 12:17

thie example:
3 1 2 1
1 1

answer
1 1


if G choose the first ring from the first row, then the first row will be dematerialised, because there is 3 and all numbers of the first row <=3. So S will win in the next move.