POJ.3537 Crosses and Crosses

1.Problem
http://poj.org/problem?id=3537

2.Idea
Calc grundy

3.Source

 int dp[2001];  
 int grundy(int n) {  
      if (n <= 0) return 0;  
      if (~dp[n]) return dp[n];  
      vector<int> vis(1 << 11);  
      for (int i = 1; i <= n; ++i) {  
           vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;  
      }  
      for (int i = 0; ; ++i) {  
           if (!vis[i]) return dp[n] = i;  
      }  
 }  
 void solve()  
 {  
      std::memset(dp, 0xff, sizeof(dp));  
      int n;  
      cin >> n;  
      cout << (grundy(n) ? 1 : 2) << endl;  
 }  

POJ.2975 Nim

1.Problem
http://poj.org/problem?id=2975

2.Idea
Calculate Nim.

3.Source

 int n;  
 int a[1100];  
 void solve()  
 {  
      while (scanf("%d", &n)) {  
           if (n == 0) break;  
           int x = 0;  
           REP(i, n) {  
                scanf("%d", &a[i]);  
                x ^= a[i];  
           }  
           int ans = 0;  
           if (x > 0) {  
                REP(i, n) {  
                     int tmp = x ^ a[i];  
                     if (tmp <= a[i]) ans++;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.1704 Georgia and Bob

 1.Problem
http://poj.org/problem?id=1704

2.Idea
Using Nim

3.Source

 int n;  
 int p[N];  
 void solve()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           REP(i, n) cin >> p[i];  
           if (n % 2) p[n++] = 0;  
           sort(p, p + n);  
           int x = 0;  
           for (int i = 0; i + 1 < n; i += 2) {  
                x ^= (p[i + 1] - p[i] - 1);  
           }  
           if (x == 0) cout << "Bob will win" << endl;  
           else cout << "Georgia will win" << endl;  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2311 Cutting Game

 1.Problem

http://poj.org/problem?id=2311

2.Idea

Using Grundy number

3.Source

 int W, H;  
 int mem[220][220];  
 int grundy(int w, int h)  
 {  
      if (mem[w][h] != -1) return mem[w][h];  
      set<int> s;  
      for (int i = 2; w - i >= 2; i++) {  
           s.insert(grundy(i, h) ^ grundy(w - i, h));  
      }  
      for (int i = 2; h - i >= 2; i++) {  
           s.insert(grundy(w, i) ^ grundy(w, h - i));  
      }  
      int res = 0;  
      while (s.count(res)) res++;  
      return mem[w][h] = res;  
 }  
 void solve()  
 {  
      memset(mem, -1, sizeof mem);  
      while (scanf("%i%i", &W, &H) > 0) {  
           if (grundy(W, H) != 0) puts("WIN");  
           else puts("LOSE");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }