题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4664
题意：给出一个n个点的凸包（不存在三点共线）。每次可以选择两个点连线，但是任意两条线只能在顶点处相交。若某一方连完线先后出现一个三角形，则该方为胜者，游戏结束。现在有若干个这样的凸包，每次双方可选择任意一个凸包连线。但是某个凸包一旦被连成一个三角形，则不能在该凸包上连线。
思路：因为若一条线的两个端点之一已经有一条线通过，则该条线连完之后必输。因此一个凸包连一条线就是将这个凸包分成两部分，因此可计算n个点时的SG值。最后发现，前69个没规律，从n=70开始循环节为34。
int SG[N];
int DFS(int n)
{
if(n<=1) return 0;
if(SG[n]!=-1) return SG[n];
int p[50]={0},i;
for(i=0;i<=n-2;i++)
{
p[DFS(i)^DFS(n-2-i)]=1;
}
i=0;
while(p[i]) i++;
return i;
}
int cal(int x)
{
if(x<=1) return 0;
return DFS(x);
}
void init()
{
clr(SG,-1);
int i;
FOR0(i,N) SG[i]=cal(i);
}
int n;
int get(int x)
{
if(x<=69) return SG[x];
x=x-69;
x=(x-1)%34+1+69;
return SG[x];
}
int main()
{
init();
rush()
{
RD(n);
int i,x,ans=0;
FOR1(i,n) RD(x),ans^=get(x);
if(ans) puts("Carol");
else puts("Dave");
}
}