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

4bitにっき

ぽよ

Game Theory (HackerRank) : Nimble Game

Nim

問題

Programming Problems and Competitions :: HackerRank
N個の箱がある。
それぞれの箱には c_{i}個の石が入っている。
2人のプレイヤーは、それぞれのターンで石を1つだけ選んでより番号の小さい箱へ移動させる。
先に操作出来なくなったほうが負けである。
勝つのはどちらか。

解法

それぞれの石をNimにおける石の山だと思ってやる。

実装

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

#define int long long

int T, N, C[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 >> C[i];
			if (C[i]&1) x ^= i;
		}
		puts(x ? "First" : "Second");
	}
	return 0;
}