A Simple Game

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 302    Accepted Submission(s): 65

Problem Description

Agrael likes play a simple game with his friend Animal during the classes. In this Game there are n piles of stones numbered from 1 to n, the 1st pile has M₁ stones, the 2nd pile has M₂ stones, … and the n-th pile contain M_n stones. Agrael and Animal take turns to move and in each move each of the players can take at most L₁ stones from the 1st pile or take at most L₂ stones from the 2nd pile or … or take L_n stones from the n-th pile. The player who takes the last stone wins.

After Agrael and Animal have played the game for months, the teacher finally got angry and decided to punish them. But when he knows the rule of the game, he is so interested in this game that he asks Agrael to play the game with him and if Agrael wins, he won’t be punished, can Agrael win the game if the teacher and Agrael both take the best move in their turn?

The teacher always moves first(-_-), and in each turn a player must takes at least 1 stones and they can’t take stones from more than one piles.

Input

The first line contains the number of test cases. Each test cases begin with the number n (n ≤ 10), represent there are n piles. Then there are n lines follows, the i-th line contains two numbers M_i and L_i (20 ≥ M_i > 0, 20 ≥ L_i > 0).

Output

Your program output one line per case, if Agrael can win the game print “Yes”, else print “No”.

Sample Input

2 1 5 4 2 1 1 2 2

Sample Output

Yes No

 哈哈，这是学校本学期ACM总决赛的第一道题目，也是我本学期第一次参加，诶~

奖品很丰厚，第一名可以拿到价值6000元的笔记本一台，跟我是无缘的了-_-!，我的水平也就能A这么一道，惭愧！不过我也满足了，谁让我没努力过呢！

大家有什么算法也拿出来交流哦，希望不吝赐教！！！！

其实老手看到这道题，肯定见过不少这种类型的题目，特别是在比较流行的ACM OJ上面，像北大，哈工大啦~类似的题目很多，算法都一样

#include<iostream>
using namespace std;
int main()
{
 int j,i,m,n,a,b,s[20],sg;
 while(cin>>n)
 {
  for(i=0;i<n;i++)
  {
   while(cin>>m&&m>0&&m<11)
   {
    sg=0;
    for(j=0;j<m;j++)
    {
     cin>>a>>b;
     s[j]=a%(b+1);
     sg=sg^s[j];
    }
    if(sg!=0)
     cout<<”No”<<endl;
    else
     cout<<”Yes”<<endl;
   }
  }
 }
 return 0;
}

大家也可以看到网上同样流行的一道题目，很类似 

C语言的取石头游戏,—-超高难度的算法题

有甲乙两个人玩取石子游戏,共有n个石子(1<=n<=30000)两个人轮流取,甲先取.每次最多取m个(1<=m<=30000)最少取一个,当轮到谁取的时候没有石子了,谁就赢.
比如4个石子,每次最多取3个,那末先取的人(甲)一定赢n和m谁大没有限制.)
(甲拿走3个,乙只拿走1个,下面轮到甲了,但是没有石子了,甲赢了．）
　现在要求你写一个程序，输入n(总的石子个数），最多可以取的石子个数m，输出甲（先取的人）是否会赢，会赢的话输出YES,否则输出LOSE.
　我们这里假设甲乙两个人都采取最好的策略，也就是甲乙都非常想赢而且足够聪明．
　比如输入４　３　输出YES
 

算法很简单：

n=k*（m+1）+1则乙赢否则甲赢（k为整数）

证明很麻烦，可以在google里找到

CODE：

#include<stdio.h>#define MAXN 30000
int a[MAXN+1];

int DPfun(int n,int m)
{
int i,k;
if(n==1)
return false;
else if( m>=(n-1) )
return true;
else{
a[1]=0;
for(i=2;i<=(m+1);i++)
a[i]=1;
for(i=(m+2); i<=n; i++)
{
for(k=1;k<=m && a[i-k];k++);
if(k>m)
a[i]=0;
else
a[i]=1;
}
return a[n];
}
} int main()
{
int n,m;
scanf(“%d %d”, &n,&m);
if(DPfun(n,m))
printf(“YES\n”);
else
printf(“LOSE\n”);return 0;
}

Popularity: 8% [?]