oj.uz

Submission #49103

# Submission time Handle Problem Language Result Execution time Memory
49103 2018-05-22T09:39:49 Z aome Bowling (BOI15_bow) C++17
49 / 100
 13 ms 1420 KB 
#include <bits/stdc++.h>

using namespace std;

int n;
int score[10];
string s;
long long f[10][305][4];

void solve() {
	cin >> n >> s;
	for (int i = 0; i < n; ++i) cin >> score[i];
	memset(f, 0, sizeof f);

	// 0 -> i - 1 ko duoc 10
	// 1 -> i - 1 duoc 10
	// 2 -> i - 1 duoc strike
 	// 3 -> i - 1 duoc strike va i - 2 duoc strike

	f[0][0][0] = 1;

	for (int i = 0; i < (n - 1); ++i) {
		for (int j = 0; j <= 300; ++j) {
			for (int k = 0; k < 4; ++k) {
				if (!f[i][j][k]) continue;

				// cout << i << ' ' << j << ' ' << k << '\n';

				char c1 = s[i * 2], c2 = s[i * 2 + 1];

				for (int m1 = 0; m1 <= 10; ++m1) {
					if (c1 == 'x' || m1 == 10) {
						if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
					}
					else if (c1 != '?') {
						if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
					}

					for (int m2 = 0; m2 + m1 <= 10; ++m2) {
						if (c2 == '-' || m1 == 10) {
							if (m1 != 10 || c2 != '?' && c2 != '-') continue;
						}
						else if (c2 == '/' || m1 + m2 == 10) {
							if (m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
						}
						else if (c2 != '?') {
							if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
						}

						if (k == 0) {
							if (m1 == 10) {
								f[i + 1][j + 10][2] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								f[i + 1][j + 10][1] += f[i][j][k];
							}
							else {
								if (score[i] != -1 && score[i] != j + m1 + m2) continue;
								f[i + 1][j + m1 + m2][0] += f[i][j][k];
							}
						}

						if (k == 1) {
							if (m1 == 10) {
								if (score[i - 1] != -1 && score[i - 1] != j + 10) continue;
								f[i + 1][j + 10 + 10][2] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								if (score[i - 1] != -1 && score[i - 1] != j + m1) continue;
								f[i + 1][j + 10 + m1][1] += f[i][j][k];
							}
							else {
								if (score[i - 1] != -1 && score[i - 1] != j + m1) continue;
								if (score[i] != -1 && score[i] != j + m1 + m2 + m1) continue;
								f[i + 1][j + m1 + m2 + m1][0] += f[i][j][k];
							}
						}

						if (k == 2) {
							if (m1 == 10) {
								f[i + 1][j + 10][3] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								if (score[i - 1] != -1 && score[i - 1] != j + 10) continue;
								f[i + 1][j + 10 + 10][1] += f[i][j][k];
							}
							else {
								if (score[i - 1] != -1 && score[i - 1] != j + m1 + m2) continue;
								if (score[i] != -1 && score[i] != j + m1 + m2 + m1 + m2) continue;
								f[i + 1][j + m1 + m2 + m1 + m2][0] += f[i][j][k];
							}
						}

						if (k == 3) {
							if (m1 == 10) {
								if (score[i - 2] != -1 && score[i - 2] != (j - 10) + 10 + 10) continue;
								f[i + 1][j + 10 + 10 + 10][3] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								if (score[i - 2] != -1 && score[i - 2] != (j - 10) + 10 + m1) continue;
								if (score[i - 1] != -1 && score[i - 1] != j + 10 + m1 + m1 + m2) continue;
								f[i + 1][j + 10 + m1 + m1 + m2 + m1 + m2][1] += f[i][j][k]; 
							}
							else {
								if (score[i - 2] != -1 && score[i - 2] != (j - 10) + 10 + m1) continue;
								if (score[i - 1] != -1 && score[i - 1] != j + 10 + m1 + m1 + m2) continue;
								if (score[i] != -1 && score[i] != j + 10 + m1 + m1 + m2 + m1 + m2) continue;
								f[i + 1][j + 10 + m1 + m1 + m2 + m1 + m2][0] += f[i][j][k];						
							}
						}
					}
				}
			}
		}
	}

	long long res = 0;

	for (int i = 0; i <= 300; ++i) {
		for (int j = 0; j < 4; ++j) {
			if (!f[n - 1][i][j]) continue;
			char c1 = s[(n - 1) * 2], c2 = s[(n - 1) * 2 + 1], c3 = s[(n - 1) * 2 + 2];

			// cout << i << ' ' << j << ' ' << f[n - 1][i][j] << '\n';

			for (int m1 = 0; m1 <= 10; ++m1) {
				if (c1 == 'x' || m1 == 10) {
					if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
				}
				else if (c1 != '?') {
					if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
				}

				// cout << m1 << '\n';

				int lim1 = 0;
				if (m1 == 10) lim1 = 10;
				else lim1 = 10 - m1;

				for (int m2 = 0; m2 <= lim1; ++m2) {
					if (c2 == 'x' || m1 == 10 && m2 == 10) {
						if (m1 != 10 || m2 != 10 || c2 != '?' && c2 != 'x') continue;
					}
					else if (c2 == '/' || m1 != 10 && m1 + m2 == 10) {
						if (m1 == 10 || m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
					}
					else if (c2 != '?') {
						if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
					}

					// cout << m1 << ' ' << m2 << '\n';

					int lim2 = 0;
					if (m1 == 10 && m2 == 10) lim2 = 10;
					else if (m1 == 10) lim2 = 10 - m2;
					else if (m1 + m2 == 10) lim2 = 10;

					for (int m3 = 0; m3 <= lim2; ++m3) {
						if (c3 == 'x' || (m1 + m2 == 10 || m1 + m2 == 20) && m3 == 10) {
							if (m1 + m2 != 10 && m1 + m2 != 20 || m3 != 10 || c3 != '?' && c3 != 'x') continue;
						}
						else if (c3 == '/' || m1 == 10 && m2 != 10 && m2 + m3 == 10) {
							if (m1 != 10 || m2 == 10 || m2 + m3 != 10 || c3 != '?' && c3 != '/') continue;
						}
						else if (c3 == '-' || m1 + m2 < 10) {
							if (m1 + m2 >= 10 || c3 != '?' && c3 != '-') continue;
						}
						else if (c3 != '?') {
							if (m3 != c3 - '0' || c3 != '?' && (c3 < '0' || c3 > '9')) continue;
						}

						// cout << m1 << ' ' << m2 << ' ' << m3 << '\n';

						if (j == 0) {
							if (score[n - 1] != -1 && i + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}

						if (j == 1) {
							if (score[n - 2] != -1 && i + m1 != score[n - 2]) continue;
							if (score[n - 1] != -1 && i + m1 + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}

						if (j == 2) {
							if (score[n - 2] != -1 && i + m1 + m2 != score[n - 2]) continue;
							if (score[n - 1] != -1 && i + m1 + m2 + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}

						if (j == 3) {
							if (score[n - 3] != -1 && (i - 10) + 10 + m1 != score[n - 3]) continue;
							if (score[n - 2] != -1 && i + 10 + m1 + m1 + m2 != score[n - 2]) continue;
							if (score[n - 1] != -1 && i + 10 + m1 + m1 + m2 + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}
					}
				}
			}
		}
	}

	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t; while (t--) solve();
}

Compilation message

bow.cpp: In function 'void solve()':
bow.cpp:33:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
                       ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:36:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:41:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 != 10 || c2 != '?' && c2 != '-') continue;
                        ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:44:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
                             ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:47:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:128:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
                      ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:131:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
                            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:141:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (c2 == 'x' || m1 == 10 && m2 == 10) {
                       ~~~~~~~~~^~~~~~~~~~~
bow.cpp:142:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 != 10 || m2 != 10 || c2 != '?' && c2 != 'x') continue;
                                   ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:144:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      else if (c2 == '/' || m1 != 10 && m1 + m2 == 10) {
                            ~~~~~~~~~^~~~~~~~~~~~~~~~
bow.cpp:145:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 == 10 || m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
                                        ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:148:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:159:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (c3 == 'x' || (m1 + m2 == 10 || m1 + m2 == 20) && m3 == 10) {
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
bow.cpp:160:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 + m2 != 10 && m1 + m2 != 20 || m3 != 10 || c3 != '?' && c3 != 'x') continue;
            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
bow.cpp:160:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 + m2 != 10 && m1 + m2 != 20 || m3 != 10 || c3 != '?' && c3 != 'x') continue;
                                                          ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:162:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       else if (c3 == '/' || m1 == 10 && m2 != 10 && m2 + m3 == 10) {
                             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
bow.cpp:163:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 != 10 || m2 == 10 || m2 + m3 != 10 || c3 != '?' && c3 != '/') continue;
                                                     ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:166:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 + m2 >= 10 || c3 != '?' && c3 != '-') continue;
                             ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:169:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m3 != c3 - '0' || c3 != '?' && (c3 < '0' || c3 > '9')) continue;
                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 852 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 4 ms 1008 KB Output is correct
4 Correct 3 ms 1120 KB Output is correct
5 Correct 3 ms 1120 KB Output is correct
6 Correct 4 ms 1120 KB Output is correct
7 Correct 4 ms 1120 KB Output is correct
8 Correct 4 ms 1120 KB Output is correct
9 Correct 3 ms 1120 KB Output is correct
10 Correct 5 ms 1120 KB Output is correct
11 Correct 4 ms 1120 KB Output is correct
12 Correct 5 ms 1120 KB Output is correct
13 Correct 3 ms 1120 KB Output is correct
14 Correct 4 ms 1120 KB Output is correct
15 Correct 4 ms 1120 KB Output is correct
16 Correct 3 ms 1120 KB Output is correct
17 Correct 5 ms 1120 KB Output is correct
18 Correct 4 ms 1120 KB Output is correct
19 Correct 4 ms 1120 KB Output is correct
20 Correct 4 ms 1120 KB Output is correct
21 Correct 3 ms 1132 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1212 KB Output is correct
2 Correct 4 ms 1216 KB Output is correct
3 Correct 5 ms 1220 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 4 ms 1232 KB Output is correct
7 Correct 4 ms 1236 KB Output is correct
8 Correct 4 ms 1324 KB Output is correct
9 Correct 3 ms 1324 KB Output is correct
10 Correct 13 ms 1324 KB Output is correct
11 Correct 11 ms 1384 KB Output is correct
12 Correct 10 ms 1384 KB Output is correct
13 Correct 11 ms 1384 KB Output is correct
14 Correct 5 ms 1384 KB Output is correct
15 Correct 4 ms 1384 KB Output is correct
16 Correct 4 ms 1384 KB Output is correct
17 Correct 4 ms 1384 KB Output is correct
18 Correct 3 ms 1384 KB Output is correct
19 Correct 3 ms 1384 KB Output is correct
20 Correct 3 ms 1384 KB Output is correct
21 Correct 3 ms 1420 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -