ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1465. Игра в пешки

I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Послано xurshid_n 17 дек 2011 17:36
Re: I precalculate nim values, and found period postion(68). But WA13. Who can help? What'is tricky?
Послано xurshid_n 18 дек 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?
Послано mwh 13 янв 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?
Послано Rafi Kamal 18 авг 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?
Послано Anish 18 июн 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