题目链接：

题意：给出一个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");

    }

}