Triangulation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 96 Accepted Submission(s): 29

Problem Description

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.

Input

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, n, ..., n.

Sum of all N <= 10.
1<=n<=10.

Output

T lines. If Carol wins the corresponding game, print 'Carol' (without quotes;) otherwise, print 'Dave' (without quotes.)

Sample Input

2
1
2
2
2 2

Sample Output

Carol
Dave

Source

2013 Multi-University Training Contest 6

Recommend

zhuyuanchen520

这题一开始看错题目意思了。

导致连SG函数转移都写不出来。

其实这题看懂了就很好搞了。

每次加边，不能形成三角形，所以肯定不加共点的边，否则就是自杀。

x个点，转移后相当于 i , x-i-2 .加的那两个点去掉了。

SG函数打表以后，很明显是要找规律。

发现周期是34.

而且周期要到后面才有周期。

所以前面打表，后面利用周期。

可以参考下oeis,发现这个是经典的问题。Sprague-Grundy values for Dawson's Chess

http://oeis.org/search?q=0%2C1%2C1%2C2%2C0%2C3%2C1%2C1%2C0%2C3%2C3%2C2%2C2%2C4%2C0%2C5%2C2%2C2%2C3%2C3%2C0&sort=&language=english&go=Search

Has period 34 with the only exceptions at n=0, 14, 16, 17, 31, 34 and 51.

然后胡搞下就过了

 /*

  * Author:  kuangbin

  * Created Time:  2013/8/8 11:54:23

  * File Name: 1010.cpp

  */

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <time.h>

 using namespace std;

 const int MAXN = ;

 int sg[MAXN];

 bool vis[MAXN];

 int mex(int x)

 {

     if(sg[x]!=-)return sg[x];

     if(x == )return sg[x] = ;

     if(x == )return sg[x] = ;

     if(x == )return sg[x] = ;

     if(x == )return sg[x] = ;

     memset(vis,false,sizeof(vis));

     for(int i = ;i < x-;i++)

         vis[mex(i)^mex(x-i-)] = true;

     for(int i = ;;i++)

         if(!vis[i])

             return sg[x] = i;

 }

 int SG(int x)

 {

     if(x <= )return sg[x];

     else

     {

         x %= ;

         x += *;

         return sg[x];

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     memset(sg,-,sizeof(sg));

     for(int i = ;i <= ;i++)

     {

         sg[i] = mex(i);

     }

     int T;

     int n;

     int a;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         int sum = ;

         for(int i = ;i < n;i++)

         {

             scanf("%d",&a);

             sum ^= SG(a);

         }

         if(sum)printf("Carol\n");

         else printf("Dave\n");

     }

     return ;

 }

2C3

HDU 4664 Triangulation（2013多校6 1010题，博弈）

Triangulation