Madiyar

Untitled

Nov 17th, 2012
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
  21. #define f0(a) memset(a, 0, sizeof(a))
  22. #define all(v) v.begin(), v.end()
  23. #define pii pair<int,int>
  24. #define vi vector<int>
  25. #define ll long long
  26.  
  27. #ifdef WIN32
  28. #define I64 "%I64d"
  29. #else
  30. #define I64 "%lld"
  31. #endif
  32.  
  33. bool calced[52][52][52][4][4][2];
  34.  
  35. int dp[52][52][52][4][4][2], a[10000], n, cnt[30];
  36.  
  37. int Win(int c0, int c1, int c2, int fi, int se, bool who) {
  38.  
  39. if (c0 == 0 && c1 == 0 && c2 == 0) {
  40. if (fi == 0 && se != 0) return 1;
  41. if (fi != 0 && se == 0) return 2;
  42. return 3;
  43. }
  44.  
  45.  
  46. int &ans = dp[c0][c1][c2][fi][se][who];
  47.  
  48. if (calced[c0][c1][c2][fi][se][who]) return ans;
  49.  
  50. // calced[c0][c1][c2][fi][se][who] = true;
  51.  
  52. int t1, t2, t3;
  53. ans = 0;
  54.  
  55. if (who == 0) {
  56.  
  57. if(c0 > 0) t1 = Win(c0 - 1, c1, c2, fi, se, !who);
  58.  
  59. if(c1 > 0) t2 = Win(c0 , c1 - 1, c2, (fi + 1) % 3, se, !who);
  60.  
  61. if(c2 > 0) t3 = Win(c0, c1, c2 - 1, (fi + 2) % 3, se, !who);
  62.  
  63. if (t1 == 1 || t2 == 1 || t3 == 1) {
  64. ans = 1;
  65. return ans;
  66. }
  67.  
  68. if (t1 == 3 || t2 == 3 || t3 == 3) {
  69. ans = 3;
  70. return ans;
  71. }
  72.  
  73. ans = 2;
  74. return ans;
  75.  
  76. } else
  77. if (who == 1) {
  78. if(c0 > 0) t1 = Win(c0 - 1, c1, c2, fi, se, !who);
  79.  
  80. if(c1 > 0) t2 = Win(c0 , c1 - 1, c2, fi, (se + 1) % 3, !who);
  81.  
  82. if(c2 > 0) t3 = Win(c0, c1, c2 - 1, fi, (se + 2) % 3, !who);
  83.  
  84. if (t1 == 2 || t2 == 2 || t3 == 2) {
  85. ans = 2;
  86. return ans;
  87. }
  88. if (t1 == 3 || t2 == 3 || t3 == 3) {
  89. ans = 3;
  90. return ans;
  91. }
  92. ans = 1;
  93. return ans;
  94.  
  95. } else
  96. assert(false);
  97. }
  98.  
  99. int main() {
  100. freopen("divisigame.in","r",stdin);
  101. freopen("divisigame.out","w",stdout);
  102. scanf("%d", &n);
  103. int x;
  104. for (int i = 0; i < n; ++i){
  105. scanf("%d", &x);
  106. while (x < 0) x += 3;
  107. cnt[x % 3]++;
  108. cerr << x % 3<< " " ;
  109. }
  110. memset(calced, 0, sizeof(calced));
  111. x = Win(cnt[0], cnt[1], cnt[2], 0, 0, 0);
  112. if (x == 1) puts("FIRST"); else
  113. if (x == 3) puts("DRAW"); else
  114. puts("SECOND");
  115.  
  116. return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment