ErnestGalbrun

Untitled

Dec 26th, 2021
531
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <compare>
  5. #include <absl/time/time.h>
  6. #include <absl/time/clock.h>
  7. #include <sstream>
  8. #include <map>
  9. #include <regex>
  10. #include <absl/algorithm/container.h>
  11. #include <absl/strings/str_split.h>
  12. #include <absl/strings/str_cat.h>
  13.  
  14. using namespace std;
  15.  
  16. long long comb(int n) {
  17.     switch (n) {
  18.         case 3:
  19.         case 9:
  20.             return 1ll;
  21.         case 4:
  22.         case 8:
  23.             return 3ll;
  24.         case 5:
  25.         case 7:
  26.             return 6ll;
  27.         case 6:
  28.             return 7ll;
  29.         default:
  30.             throw std::invalid_argument("wrong n");
  31.     }
  32. }
  33.  
  34. long long S[2][10][10][31][31];
  35.  
  36. // p: whose turn it is to play
  37. // l/r: position of player 0/1
  38. // sl/sr: score of player 0/1
  39. long long get(int p, int l, int r, int sl, int sr) {
  40.     if (S[p][l][r][sl][sr] != -1ll) return S[p][l][r][sl][sr];
  41.     int prev = (p + 1) % 2;
  42.     long long ans = 0ll;
  43.     if (sl >= 21 && sr >= 21) return 0ll;
  44.     if (prev == 0) {
  45.         if ((sl - (l + 1) < 0) || (sl - (l + 1) >= 21)) return 0ll;
  46.         for (int d = 3; d <= 9; ++d) {
  47.             ans += comb(d) * get(0, (l + 10 - d) % 10, r, sl - (l + 1), sr);
  48.         }
  49.     } else {
  50.         if ((sr - (r + 1) < 0) || (sr - (r + 1) >= 21)) return 0ll;
  51.         for (int d = 3; d <= 9; ++d) {
  52.             ans += comb(d) * get(1, l, (r + 10 - d) % 10, sl, sr - (r + 1));
  53.         }
  54.     }
  55.     S[p][l][r][sl][sr] = ans;
  56.     return ans;
  57. }
  58.  
  59. int main() {
  60.     auto start = absl::Now();
  61.  
  62.     for (int sl = 0; sl < 31; ++sl) {
  63.         for (int sr = 0; sr < 31; ++sr) {
  64.             for (int p = 0; p < 2; ++p) {
  65.                 for (int l = 0; l < 10; ++l) {
  66.                     for (int r = 0; r < 10; ++r) {
  67.                         S[p][l][r][sl][sr] = -1ll;
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     S[0][1][9][0][0] = 1ll;
  74.  
  75.     long long total_left = 0;
  76.     for (int sl = 21; sl <= 31; ++sl) {
  77.         for (int sr = 0; sr < 21; ++sr) {
  78.             for (int l = 0; l < 10; ++l) {
  79.                 for (int r = 0; r < 10; ++r) {
  80.                     total_left += get(1, l, r, sl, sr);
  81.                 }
  82.             }
  83.         }
  84.     }
  85.  
  86.     long long total_right = 0;
  87.     for (int sl = 0; sl < 21; ++sl) {
  88.         for (int sr = 21; sr < 31; ++sr) {
  89.             for (int l = 0; l < 10; ++l) {
  90.                 for (int r = 0; r < 10; ++r) {
  91.                     total_right += get(0, l, r, sl, sr);
  92.                 }
  93.             }
  94.         }
  95.     }
  96.  
  97.     cout << max(total_left, total_right) << endl;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment