Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <compare>
- #include <absl/time/time.h>
- #include <absl/time/clock.h>
- #include <sstream>
- #include <map>
- #include <regex>
- #include <absl/algorithm/container.h>
- #include <absl/strings/str_split.h>
- #include <absl/strings/str_cat.h>
- using namespace std;
- long long comb(int n) {
- switch (n) {
- case 3:
- case 9:
- return 1ll;
- case 4:
- case 8:
- return 3ll;
- case 5:
- case 7:
- return 6ll;
- case 6:
- return 7ll;
- default:
- throw std::invalid_argument("wrong n");
- }
- }
- long long S[2][10][10][31][31];
- // p: whose turn it is to play
- // l/r: position of player 0/1
- // sl/sr: score of player 0/1
- long long get(int p, int l, int r, int sl, int sr) {
- if (S[p][l][r][sl][sr] != -1ll) return S[p][l][r][sl][sr];
- int prev = (p + 1) % 2;
- long long ans = 0ll;
- if (sl >= 21 && sr >= 21) return 0ll;
- if (prev == 0) {
- if ((sl - (l + 1) < 0) || (sl - (l + 1) >= 21)) return 0ll;
- for (int d = 3; d <= 9; ++d) {
- ans += comb(d) * get(0, (l + 10 - d) % 10, r, sl - (l + 1), sr);
- }
- } else {
- if ((sr - (r + 1) < 0) || (sr - (r + 1) >= 21)) return 0ll;
- for (int d = 3; d <= 9; ++d) {
- ans += comb(d) * get(1, l, (r + 10 - d) % 10, sl, sr - (r + 1));
- }
- }
- S[p][l][r][sl][sr] = ans;
- return ans;
- }
- int main() {
- auto start = absl::Now();
- for (int sl = 0; sl < 31; ++sl) {
- for (int sr = 0; sr < 31; ++sr) {
- for (int p = 0; p < 2; ++p) {
- for (int l = 0; l < 10; ++l) {
- for (int r = 0; r < 10; ++r) {
- S[p][l][r][sl][sr] = -1ll;
- }
- }
- }
- }
- }
- S[0][1][9][0][0] = 1ll;
- long long total_left = 0;
- for (int sl = 21; sl <= 31; ++sl) {
- for (int sr = 0; sr < 21; ++sr) {
- for (int l = 0; l < 10; ++l) {
- for (int r = 0; r < 10; ++r) {
- total_left += get(1, l, r, sl, sr);
- }
- }
- }
- }
- long long total_right = 0;
- for (int sl = 0; sl < 21; ++sl) {
- for (int sr = 21; sr < 31; ++sr) {
- for (int l = 0; l < 10; ++l) {
- for (int r = 0; r < 10; ++r) {
- total_right += get(0, l, r, sl, sr);
- }
- }
- }
- }
- cout << max(total_left, total_right) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment