SPOJ-MCOINS

hi friends today i will teach u how to deal with ALGORITHMIC GAMES..

the spoj link of the question...

so how to think.....
if for example inputs are

 3 4 5
12 3223 12212 34344 43434


We can see that n = 1, 3, 4 are winning positions for the first player, because he can simply take all the coins. For n=0 there are no possible moves — the game is finished — so it is the losing position for the first player, because he can not make a move from it. If n=2 the first player has only one option, to remove 1 coin. If n=5 or 6 a player can move to 2 (by removing 3 or 4 coins), and he is in a winning position. If n=7 a player can move only to 3, 4, 6, but from all of them his opponent can win.

 see the table below:
F=false,T=true;
                                               0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
                                               F  T   F  T   T   T   T  F   T   F

i think you do it still if have any query ask me... :)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include<bits/stdc++.h> using namespace std; int min(int x,int y) { return (x<y)?x:y; } int main() { int n,m,q; static bool a[1000000]; scanf("%d %d %d",&n,&m,&q); a[0]=false,a[1]=true,a[n]=true,a[m]=true; for(int i=2;i<=1000000;i++) { if(i>=1) { if(a[i-1]==true)a[i]=false; else {a[i]=true;continue;} } if(i>=n) { if(a[i-n]==true)a[i]=false; else {a[i]=true;continue;} } if(i>=m) { if(a[i-m]==true)a[i]=false; else {a[i]=true;continue;} } } while(q--) { scanf("%d",&n); printf("%c",(a[n])?'A':'B'); } return 0; }