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

4bitにっき

ぽよ

Game Theory (HackerRank) : Poker Nim

Nim

問題

Programming Problems and Competitions :: HackerRank
n個のチップの山がある。
それぞれの山には c_{i}個のチップがある。
2人のプレイヤーは、それぞれのターンで1個の山を選び、1つ以上のチップを取り除くか加えるかする。
ただし、各プレイヤーは、どんな山においてもK回以上の追加操作は出来ない。
先に操作の出来なくなったほうが負けである時、勝つのはどちらか。

 テストケース数T \leq 100
 n, k \leq 100
 1 \leq c_{i} \leq 10^9

解法

Nimと同じで、各山のサイズのXORを取る。
増やされても1手で元に戻せることと、増やされる操作は有限回しか行われないことから、増える操作は完全に無視できる。

実装

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

#define int long long

int T, N, K, C[100];

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