#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
int parse(int a, int b, int c, vi& sm, vi& sco) {
int n=sm.size();
if ((sco[2*n-2]!=-1 && sco[2*n-2]!=a) || (sco[2*n-1]!=-1 && sco[2*n-1]!=b) || (sco[2*n]!=-1 && sco[2*n]!=c)) {
return -1;
}
if (a==10) {
if (b==10) {
if (sm[n-1]!=-1) {
return sm[n-1]-a-b-c;
}
return -1e9;
}
else if (b+c<=10) {
if (sm[n-1]!=-1) {
return sm[n-1]-a-b-c;
}
return -1e9;
}
}
else if (a+b==10) {
if (sm[n-1]!=-1) {
return sm[n-1]-a-b-c;
}
return -1e9;
}
else if (a+b<10 && c==0) {
if (sm[n-1]!=-1) {
return sm[n-1]-a-b-c;
}
return -1e9;
}
return -1;
}
int parse2(int i, int a, int b, int s, int a2, int b2, vi& sm, vi& sco) {
int n=sm.size();
if ((sco[2*i]!=-1 && sco[2*i]!=a) || (sco[2*i+1]!=-1 && sco[2*i+1]!=b)) {
return -1;
}
if (a==10 && b==0) {
return s-a-a2-b2;
}
else if (a+b==10) {
return s-a-b-a2;
}
else if (a+b<10) {
return s-a-b;
}
return -1;
}
void solve() {
int n;
cin >> n;
vi sco(2*n+1);
vi sm(n);
char c;
for (int i=0; i<2*n+1; i++) {
cin >> c;
if (c=='?') {
sco[i]=-1;
}
else if (c=='/') {
sco[i]=10-sco[i-1];
}
else if (c=='-') {
sco[i]=0;
}
else if (c=='x') {
sco[i]=10;
}
else {
sco[i]=c-'0';
}
}
for (int i=0; i<n; i++) {
cin >> sm[i];
}
ll dp[n][30*n+1][11][11];
memset(dp,0,sizeof(dp));
for (int i=0; i<11; i++) {
for (int j=0; j<11; j++) {
for (int k=0; k<11; k++) {
int t=parse(i,j,k,sm,sco);
if (t==-1e9) {
for (int l=0; l<=30*n; l++) {
dp[n-1][l][i][j]++;
}
}
else if (t>=0) {
dp[n-1][t][i][j]++;
}
}
}
}
for (int i=n-2; i>=0; i--) {
for (int j=0; j<11; j++) {
for (int k=0; k<11; k++) {
for (int s=0; s<=30*n; s++) {
for (int j2=0; j2<11; j2++) {
for (int k2=0; k2<11; k2++) {
int t=parse2(i,j,k,s,j2,k2,sm,sco);
if (t>=0) {
dp[i][t][j][k]+=dp[i+1][s][j2][k2];
}
}
}
}
}
}
}
ll ans=0;
for (int i=0; i<11; i++) {
for (int j=0; j<11; j++) {
ans+=dp[0][0][i][j];
}
}
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
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... |