You are not logged in. Please login at www.codechef.com to post your questions!

×

HELP : Game Theory / Grundy Number

I am trying to solve this problem : http://www.spoj.com/problems/MATGAME/

I read all the available entries. I can't figure out where is mistake in my code.

Strategy used:

  1. Calculated grundy value for each possible cell entry

void solve() {

grundy[0] = 0;

for(int i = 1; i <= 51; ++i) {

    memset(used, false, sizeof(used));

    int mex = 0;
    for(int j = 1; j <= i; ++j)
        used[grundy[i - j]] = true;

    while(used[mex])
        ++mex;

    grundy[i] = mex;
    for(int j = i + 1; j <= 51; ++j)
        grundy[j] = grundy[i];
}

}

  1. Then for each row calculated it's grundy number and xor-ed them.

int main() {

solve();

int test, n, m, item;                           // n rows, m columns
scanf("%d", &test);

while(test--) {

    scanf("%d%d", &n, &m);                   
    int gr_overall = 0;                        // NIM sum

    for(int i = 0; i < n; ++i) {

        int mex = 1;                          // Tried mex = 0 also gives WA
        memset(used, false, sizeof(used));

        for(int j = 0; j < m; ++j) {
            scanf("%d", &item);
            used[grundy[item]] = true;         // Marking grundy number for each cell
        }

        while(used[mex]) ++mex;                // Calculating minimum value

        gr_overall ^= mex;                     // Calcualting NIM sum

    }

    if(gr_overall) cout << "FIRST" << endl;
    else cout << "SECOND" << endl;

}

return 0;

}

Please help. Thank you.

asked 19 Mar '14, 18:46

codemex's gravatar image

2★codemex
112
accept rate: 0%


What about this case?

1 1 2 1 2

link

answered 20 Jun '16, 03:51

nabil1997's gravatar image

3★nabil1997
11111716
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×323
×140
×56
×13

question asked: 19 Mar '14, 18:46

question was seen: 1,746 times

last updated: 20 Jun '16, 03:51