uva_10404-Bachet's Game

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-15
[cpp] 
/**博弈题。。这种题目的特点就是——想到方法后很简单,想不到
 *就做不出了。。开始想穷举法列出所有结果,后来发现数据量太大
 *行不通,后来看了看博弈相关东西,突然灵光一闪,想到只考虑当前
 *步,把总数为1~count时先手的输赢标记起来,方程为:
 *  if(i-a[i] == 0 || !num[i-a[i]](i-a[i]>0)) 先手赢
 *就是刚好一次可以移动完,或者移动一次后,对手必输
 */ 
#include <cstdio> 
#include <cstring> 
using namespace std; 
 
#define MAX 12 
#define MAXC 121 
 
int a[MAX]; 
int num[MAXC]; 
 
 
void move_stones(int count, int type){ 
    for(int i = 1; i <= count; i ++){ 
        for(int j = 0; j < type; j ++){ 
            if( i - a[j] > 0 && !num[i-a[j]] ){ 
                num[i] = 1; 
                break; 
            }else if( i - a[j] == 0 ){ 
                num[i] = 1; 
                break; 
            } 
        } 
    } 
    if( num[count] ) 
        printf("Stan wins/n"); 
    else 
        printf("Ollie wins/n"); 

 
int main(int argc, char const *argv[]) 

#ifndef ONLINE_JUDGE 
        freopen("test.in", "r", stdin); 
#endif 
    int count, type; 
    while( ~scanf("%d", &count) ){ 
        memset(num, 0, sizeof(num)); 
        scanf("%d", &type); 
        for(int i = 0; i < type; i ++) 
            scanf("%d", &a[i]); 
        move_stones(count, type); 
    } 
    return 0;