ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1465. Pawn Game

I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Posted by xurshid_n 17 Dec 2011 17:36
Re: I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Posted by xurshid_n 18 Dec 2011 16:52
I, found, my bug. :)
Re: I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Posted by mwh 13 Jan 2012 18:21
I get TLE for test13,it is because that my idea is to circulate all the SG-values.
Can you give me some ideas?Thank you so much.
Re: I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Posted by Rafi Kamal 18 Aug 2013 17:17
I've also using a period of 68, but WA 36

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<utility>
#include<cstdlib>
#include<string>
#include<set>
#include<limits>
#include<iomanip>
#include<fstream>
#include<sstream>
#define INF 2147483647
#define LLD int
#define clr(a) memset(a,0,sizeof(a))
#define reset(a) memset(a,-1,sizeof(a))
#define BD(i, j) (i >= 0 && i < N && j >= 0 && j < M)
#define PRINT_VAR(X) (cout << #X << " -> " << X << endl)
#define PI acos(0)
#define MAX_INT 2147483647
#define SIZE 1005
#define MOD 1000000009

using namespace std;
int X[] = {0, 1, 0, -1};
int Y[] = {1, 0, -1, 0};
/* right, down, lft, up */
int M, N;
long long res;
typedef pair<int, int> Point;

int dp[SIZE];

int solve(int n) {
    if (dp[n] == -1) {
        set<int> s;
        s.insert(solve(n - 2));
        for (int i = 2; i < n; i++) {
            s.insert(solve(i-2) ^ solve(n-i-1));
        }
        dp[n] = 0;
        while (s.find(dp[n]) != s.end())
            dp[n]++;
    }

    return dp[n];
}

int main()
{
    int t, tc, x, y, z;
    int i, j, k, l, h;
    char ch;

#ifndef ONLINE_JUDGE
       //freopen("input.txt", "r", stdin);
#endif

    reset(dp);
    dp[0] = 0;
    dp[1] = dp[2] = 1;
    cin >> N;
    cout << (solve(N % 68) ? "White" : "Black") << endl;

    return 0;
}
Re: I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Posted by Anish 18 Jun 2020 17:23
I changed
```
    cout << (solve(N % 68) ? "White" : "Black") << endl;

```

to
```
    cout << (solve(N % (68*2)) ? "White" : "Black") << endl;
```
and it got AC