UVA10404 | magicat

由题意可知，这题和巴什博弈没什么关系了

相似题目：AtCoder Beginner Contest 278 F - Shiritori

预备知识：DP，博弈论的必胜态和必败态

问题的关键是确定(f_n)是必胜态还是必败态?
而必胜态由必败态转移而来

如果当前(i-a_j)这个位置是必败态，那么(i)这个位置就是必胜态
由于(m)比较多，我们考虑用DP来转移状态
其中0代表必败态，1代表必胜态
转移方程 $f_i=1 $ ((0≤i-a_j,f_{i-a_{j}}=0))
单个数据的时间复杂度 (O(mn))

//  AC one more times
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e6+10;
int a[11],n,m,f[N];
int main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    // 特殊输入 请注释上方，如__int128等
    int TC = 1;
    while(cin>>n)
    {
    	cin>>m;
    	for(int i=1;i<=m;i++)	cin>>a[i];
    	for(int i=1;i<=n;i++)	f[i]=0;
    	// 0 代表必输态
    	// 1 代表必胜态
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			if(i>=a[j]&&f[i-a[j]]==0)
    				f[i]=1;
    	if(f[n])
    		cout<<"Stan wins"<<endl;
    	else cout<<"Ollie wins"<<endl;
    }
    return 0;
}