# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
49103 | aome | Bowling (BOI15_bow) | C++17 | 13 ms | 1420 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |