2015
09-17

# Triangulation

There are n points in a plane, and they form a convex set.

No, you are wrong. This is not a computational geometry problem.

Carol and Dave are playing a game with this points. (Why not Alice and Bob? Well, perhaps they are bored. ) Starting from no edges, the two players play in turn by drawing one edge in each move. Carol plays first. An edge means a line segment connecting two different points. The edges they draw cannot have common points.

To make this problem a bit easier for some of you, they are simutaneously playing on N planes. In each turn, the player select a plane and makes move in it. If a player cannot move in any of the planes, s/he loses.

Given N and all n’s, determine which player will win.

First line, number of test cases, T.
Following are 2*T lines. For every two lines, the first line is N; the second line contains N numbers, n1, …, nN.

Sum of all N <= 106.
1<=ni<=109.

First line, number of test cases, T.
Following are 2*T lines. For every two lines, the first line is N; the second line contains N numbers, n1, …, nN.

Sum of all N <= 106.
1<=ni<=109.

2
1
2
2
2 2

Carol
Dave

sg函数暴力求法：

#include <cstdio>
#include <cstring>
typedef long long ll;
#define N 1002
bool vis[N];
int sg[N];
int a[] = {4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7};
int SG(int x) {
if (sg[x] != -1) return sg[x];
if (x == 0) return 0;
if (x == 1) return 0;
if (x == 2) return 1;
if (x == 3) return 1;
memset(vis, false, sizeof(vis));
for (int i=0; i<x-1; i++) vis[SG(i)^SG(x-i-2)] = true;
for (int i=0; ;i++) if (!vis[i]) return i;
}
int get_sg(int x) {
if (x <= 100) return sg[x];
return a[x%34];
}
int main() {
memset(sg, -1, sizeof(sg));
for (int i=0; i<=100; i++) sg[i] = SG(i);

int T, n, x; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int ans = 0;
while (n--) { scanf("%d", &x); ans ^= get_sg(x); }
puts(ans ? "Carol" : "Dave");
}
return 0;
}