uva_10404-Bachets Game

[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; 
}