Thursday 27 July 2017

Lightoj 1199 - Partitioning Game

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int dp[10005];
  4. int cal(int n){
  5.     if(n<=2){
  6.         return 0;
  7.     }
  8.     if(dp[n]!= -1){
  9.         return dp[n];
  10.     }
  11.     set<int>s;
  12.     for(int a = 1,b = n-1; a<b; a++, b--){
  13.         s.insert(cal(a)^cal(b));
  14.     }
  15.     int ans = 0;
  16.     while(s.find(ans)!= s.end()) ans++;
  17.     return dp[n] =  ans;
  18. }
  19.  
  20. int main()
  21. {
  22.     int tc;
  23.     cin>>tc;
  24.     memset(dp, -1sizeof(dp));
  25.     for(int p = 0; p < tc; ++p){
  26.     int n;
  27.     cin>>n;
  28.     int ans = 0;
  29.     for(int i = 0; i <n; i++){
  30.         int a;
  31.         cin>>a;
  32.         ans^= cal(a);
  33.     }
  34.     if(ans) cout<<"Case "<<(p+1)<<": "<<"Alice"<<endl;
  35.     else cout<<"Case "<<(p+1)<<": "<<"Bob"<<endl;
  36.     }
  37.     return 0;
  38. }
  39.  

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...