#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10;
const int S = 300;
const int K = 13;
const char *AA = "0123456789x-/";
char aa[N * 2 + 2]; int ss[N];
long long dp[S + 1][K][K][2], dq[S + 1][K][K][2];
bool check2(char a, char b) {
if (a == 'x')
return b == '-';
if (!isdigit(a))
return false;
if (b == '/')
return true;
if (!isdigit(b))
return false;
return a - '0' + b - '0' < 10;
}
int geta(char a) {
return a == 'x' ? 10 : a - '0';
}
int getb(char a, char b) {
return b == '/' ? 10 - (a - '0') : b - '0';
}
int calc(char a, char b) {
return a == 'x' || b == '/' ? 10 : a - '0' + b - '0';
}
int count(char a, char b) {
return a == 'x' ? 2 : b == '/' ? 1 : 0;
}
bool check3(char a, char b, char c) {
if (a == 'x' && b == 'x' && c == 'x')
return true;
if (a == 'x' && b == 'x')
return isdigit(c);
if (a == 'x' && c == '/')
return isdigit(b);
if (a == 'x')
return isdigit(b) && isdigit(c) && b - '0' + c - '0' < 10;
if (b == '/' && c == 'x')
return isdigit(a);
if (b == '/')
return isdigit(a) && isdigit(c);
return isdigit(a) && isdigit(b) && c == '-' && a - '0' + b - '0' < 10;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int t; cin >> t;
while (t--) {
int n; cin >> n >> aa;
for (int i = 0; i < n; i++)
cin >> ss[i];
for (int s = 0; s <= S; s++)
for (int ha = 0; ha < K; ha++)
for (int hb = 0; hb < K; hb++)
for (int f = 0; f <= 1; f++)
dp[s][ha][hb][f] = 0;
dp[0][0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int s = 0; s <= S; s++)
for (int ha = 0; ha < K; ha++)
for (int hb = 0; hb < K; hb++)
for (int f = 0; f <= 1; f++)
dq[s][ha][hb][f] = 0;
if (i + 1 < n) {
char c_ = aa[i * 2], d_ = aa[i * 2 + 1];
for (int s = 0; s <= S; s++)
for (int ha = 0; ha < K; ha++)
for (int hb = 0; hb < K; hb++)
for (int f = 0; f <= 1; f++) {
long long x = dp[s][ha][hb][f];
if (x) {
char a = AA[ha], b = AA[hb];
for (int hc = 0; hc < K; hc++) {
char c = AA[hc];
if (c_ == '?' || c == c_)
for (int hd = 0; hd < K; hd++) {
char d = AA[hd];
if ((d_ == '?' || d == d_) && check2(c, d)) {
int s_ = s + (f ? geta(c) : 0);
if (i < 2 || s_ == ss[i - 2]) {
int t = s_ + calc(a, b), g = 0, k = count(a, b);
if (k)
t += geta(c);
if (k >= 2)
if (c == 'x')
g = 1;
else
t += getb(c, d);
dq[t][hc][hd][g] += x;
}
}
}
}
}
}
} else
break;
for (int s = 0; s <= S; s++)
for (int ha = 0; ha < K; ha++)
for (int hb = 0; hb < K; hb++)
for (int f = 0; f <= 1; f++)
dp[s][ha][hb][f] = dq[s][ha][hb][f];
/*
cout << ">>> " << i + 1 << endl;
for (int s = 0; s <= S; s++)
for (int ha = 0; ha < K; ha++)
for (int hb = 0; hb < K; hb++)
for (int f = 0; f <= 1; f++)
if (dp[s][ha][hb][f])
cout << s << ' ' << AA[ha] << AA[hb] << ' ' << f << ": " << dp[s][ha][hb][f] << endl;
*/
}
long long ans = 0;
for (int s = 0; s <= S; s++)
for (int ha = 0; ha < K; ha++)
for (int hb = 0; hb < K; hb++)
for (int f = 0; f <= 1; f++)
ans += dp[s][ha][hb][f];
cout << ans << '\n';
}
return 0;
}
# | 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... |