読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

Game Theory (HackerRank) : Nim Game

問題

Programming Problems and Competitions :: HackerRank
一般的なNimゲーム。

解法

Nimゲーム。蟻本参照。

ここでNimが出てくるということは、このコンテストのこれより前の問題をGrundy数で殴っていたのは全部想定解法ではない...?

実装

#include <bits/stdc++.h>
using namespace std;

#define int long long

int T, N, S[100];

signed main()
{
    cin >> T;
    for (int tc = 0; tc < T; tc++)
    {
        cin >> N;
        int x = 0;
        for (int i = 0; i < N; i++)
        {
            cin >> S[i];
            x ^= S[i];
        }
        puts(x ? "First" : "Second");
    }
    return 0;
}