zcmu 1466 lucky boy

1466: Lucky Boy

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 40  Solved: 17
[Submit][Status][Web Board]

Description

Recently, Lur have a good luck. He is also the cleverest boy in his school as he create the most popular computer game – Lucky Boy. The game is played by two players, a and b, in 2d planar .In the game Lucky Boy, there are n different points on plane, each time one can remove one or multiple co-line points from the plane. The one who can firstly remove more than two points from the plane wins. The one who removes the last point on the plane can also win the game. You may assume that two players are both clever enough that they can always make the best choice. The winner is called Lucky Boy. Given the n points, can you tell me who will be the Lucky Boy ? Note that player a will always the first one to remove points from the plane.

Input

The first line of each case is an integer n(0

Output

Output “a is the lucky boy.” in a single line if a win the game, otherwise you should output  “b is the lucky boy.” in a single line.

Sample Input

3 0 0 1 1 2 2 3 0 0 1 1 2 3

Sample Output

a is the lucky boy. b is the lucky boy.

 题目大意：A和B一起玩游戏。 这个游戏要求，有 n 个石头，每次可以拿一条直线上面的所有石头，一次拿3个及以上的人可以赢，或最后一次拿完石头的人可以赢。A先拿，只要有3个石头同一条线，A赢，如果没有三个石头同一条线，就开始博弈了。如果剩下1或2个石头，最后一拿必赢，因此想要自己赢，就得让对手拿的时候是3块石头。于是石头数是3的倍数时为奇异局势。如有6个石头，A可以拿1或2个，那么B只要让剩下的是3个就能赢。于是，如果石头是3的倍数，A必输。

#include
#define ll long long
#define ve vector
#define mp map
#define NO cout<<"NO"<=a;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define st string
#define N 10005
#define eps 1e-13
using namespace std;
const double pi =acos(-1.0);
const int maxn=1e6+5;
const ll mod =1e15;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
//set s;
ve v;
priority_queue, greater >q;
int lcm(int a,int b){
    return a*b/__gcd(a,b);
}
bool isleaf(int x){
     return x%400==0||(x%4==0&&x%100==0);
}
int primes[N], cnt;
bool vis[N];
void is_prime(int x){
    vis[1] = vis[0] = 1;
    for(int i = 2; i <= x; ++ i){
        if(!vis[i])primes[cnt ++ ] = i;
        for(int j = 0; primes[j] * i <= x; ++ j){
            vis[primes[j] * i] = true;
            if(i % primes[j] == 0)break;
        }
    }
}//1e6;
ll qpow(ll a,ll n)//快速幂 ll mod=1e15;
{
    ll re=1;
    while(n)
    {
        if(n&1)
            re=(re*a)%mod;
        n>>=1;
        a=(a*a)%mod;
    }
    return re;
}
inline ll qmul(ll x,ll y,ll p)//快速乘 
{
    ll z=(long double)x/p*y;
    ll res=(unsigned long long)x*y-(unsigned long long)z*p;
    return (res+p)%p;
}
void pprint(char *);
struct ob
{
	char MC[100];
	double DJ;
	int SL;
};

int sum[maxn];
void iprime(){
	mem(sum,1);
	pre(i,2,maxn/2)
 	   for(int j=i*2;j>n){
        pre(i,1,n)cin>>dp[i].x>>dp[i].y;//石子的方位 
        bool flag=false;
        if(n%3)flag=true;//不是3的倍数，A赢 
        else{
            for(int i=1;i<=n&&!flag;i++)
                for(int j=i+1;j<=n&&!flag;j++)
                    for(int k=j+1;k<=n&&!flag;k++)
                        if((dp[i].x-dp[j].x)*(dp[i].y-dp[k].y)==(dp[i].x-dp[k].x)*(dp[i].y-dp[j].y))
                            flag=true;//石子连成一条线时取，A赢,没有则B赢 
        }
        if(flag)cout<<"a is the lucky boy."<