一开始有一个数n(1<=n<=1000000)，两个人轮流对n 进行操作。每次可将n减去它的最大或最小的非零数位。

现在给定G个N，问先手赢还是输。

一道博弈问题，脑子一定要清晰，别想着想着自己乱了，那就太惨了。

必败态和必胜态很好找，考试时就写了一个记忆化的博弈搜索树，结果悲剧的栈崩了两个点。

其实可以转化成DP，f[i]为true表示i必胜，则f[i]=(not f[i-min[i]]) or (not f[i-max[i]])，实现很简单了。

粘上我的博弈搜索记忆树··············

1 program cdgame(input,output);  2 var  3    f : array[0..1010000] of longint;  4    n : longint;  5 function get_max(x: longint ):longint;  6 var  7    s  : ansistring;  8    i  : longint;  9    ch : char; 10 begin 11    ch:='0'; 12    str(x,s); 13    for i:=1 to length(s) do 14       if (s[i]>ch)and(s[i]<>'0') then 15      ch:=s[i]; 16    s:=''; 17    s:=s+ch; 18    val(s,get_max); 19 end; {
      get_max } 20 function get_min(x :longint ):longint; 21 var 22    s  : ansistring; 23    i  : longint; 24    ch : char; 25 begin 26    ch:='a'; 27    str(x,s); 28    for i:=1 to length(s) do 29       if (s[i]
      
       <>'0') then 30      ch:=s[i]; 31    s:=''; 32    s:=s+ch; 33    val(s,get_min); 34 end; {
      get_min } 35 function dfs(people,now : longint ):longint; 36 begin 37    if people=1 then 38    begin 39       if f[now]<>-1 then 40      exit(f[now]); 41       if dfs(1-people,now-get_max(now))*dfs(1-people,now-get_min(now))=0 then 42      f[now]:=1 43       else 44      f[now]:=0; 45       exit(f[now]); 46    end 47    else 48    begin 49       if f[now]<>-1 then 50      exit(f[now]); 51       if dfs(1-people,now-get_max(now))*dfs(1-people,now-get_min(now))=0 then 52      f[now]:=1 53       else 54      f[now]:=0; 55       exit(f[now]); 56    end; 57 end; {
      dfs } 58 procedure main; 59 var 60    i,x : longint; 61 begin 62    for i:=1 to 1000000 do 63       f[i]:=-1; 64    f[0]:=0; 65    readln(n); 66    for i:=1 to n do 67    begin 68       readln(x); 69       if dfs(1,x)=1 then 70      writeln('win') 71       else 72      writeln('failed'); 73    end; 74 end; {
      main } 75 begin 76    assign(input,'cdgame.in');reset(input); 77    assign(output,'cdgame.out');rewrite(output); 78    main; 79    close(input); 80    close(output); 81 end.