백준 16187 (C++) Game on Plane

최초 업로드: 2025-09-17 23:56:37

최근 수정 시간: 2025-09-17 23:56:37

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] Game on Plane

[문제 링크](https://www.acmicpc.net/problem/16187)

## 문제 설명

You are given $N$ points on a plane. These points are precisely the set of vertices of some regular $N$-gon. Koosaga, an extreme villain, is challenging you with a game using these points. You and Koosaga alternatively take turns, and in each turn, the player

<ol>
	<li>chooses two of the given points, then</li>
	<li>draws the line segment connecting the two chosen points.</li>
</ol>

Also, the newly drawn line segment must not intersect with any of the previously drawn line segments in the interior. It is possible for two segments to meet at their endpoints. If at any point of the game, there exists a convex polygon consisting of the drawn line segments, the game ends and the last player who made the move wins.

Given the integer $N$, Koosaga is letting you decide who will move first. Your task is decide whether you need to move first or the second so that you can win regardless of Koosaga's moves.

## 입력

The input consists of many test cases. The first line contains an integer $T$ ($1\leq T\leq 5,000$), the number of test cases. Each of the following $T$ test cases is consisted of one line containing the integer $N$ ($3\leq N\leq 5,000$).

## 출력

For each test case, print one line containing the string <code><samp>First</samp></code> if you need to move first or <code><samp>Second</samp></code> if you need to move second so that you can win regardless of Koosaga's moves.

## 풀이
[백준 13034번](https://projectbpm.kro.kr/read/303) 문제와 같은 문제이다.

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

int g[5001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

g[2]=1;
 for(int i=3;i<=5000;i++) {
 set<int> grundies;
 for(int j=0;j<=i-2;j++) grundies.insert(g[j]^g[i-2-j]);
 for(int j=0;;j++) {
 if(!grundies.count(j)) {
 g[i]=j;
 break;
 }
 }
 }

int t; cin >> t;
 while(t--) {
 int n; cin >> n;
 cout << (g[n] ? "First\n" : "Second\n");
 }
}
```