#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
int dp[11][301][11][11][32];
int sdp[11][301][31][11],sumdp[11][301][31];
int n;
char a[25];
int v[15];
bool kk[105][105][105];
bool vaz[105][105][105];
bool ok(int x,int pos,int prec)
{
if (vaz[x + 1][pos][prec + 1])
return kk[x + 1][pos][prec + 1];
vaz[x + 1][pos][prec + 1] = true;
if (a[pos] == '?')
{
kk[x + 1][pos][prec + 1] = true;
return true;
}
char cx;
if (x == -1)
cx = '-';
else if (prec == -1)
{
if (x >= 0 and x <= 9)
cx = (char)('0' + x);
else
cx = 'x';
}
else
{
if (x + prec < 10)
cx = (char)('0' + x);
else
cx = '/';
}
if (cx == a[pos])
{
kk[x + 1][pos][prec + 1] = true;
return true;
}
kk[x + 1][pos][prec + 1] = false;
return false;
}
bool okv(int x,int pos)
{
if (v[pos] == -1)
return true;
if (x == v[pos])
return true;
return false;
}
int f(int c11,int c12,int c21,int c22)
{
if (c11 == 10)
{
if (c12 != c21)
return 31;
return 10 + c21 + c22;
}
if (c11 + c12 < 10)
return c11 + c12;
else if (c11 + c12 > 10)
return 31;
return 10 + c21;
}
void testcase()
{
for (int i = 0; i < 105; i++)
for (int j = 0; j < 105; j++)
for (int k = 0; k < 105; k++)
kk[i][j][k] = vaz[i][j][k] = false;
for (int i = 0; i < 11; i++)
for (int j = 0; j < 301; j++)
for (int ii = 0; ii < 11; ii++)
for (int jj = 0; jj < 11; jj++)
for (int kkk = 0; kkk < 32; kkk++)
dp[i][j][ii][jj][kkk] = 0;
for (int i = 0; i < 11; i++)
for (int j = 0; j < 301; j++)
for (int ii = 0; ii < 31; ii++)
for (int jj = 0; jj < 11; jj++)
sdp[i][j][ii][jj] = 0;
for (int i = 0; i < 11; i++)
for (int j = 0; j < 301; j++)
for (int ii = 0; ii < 31; ii++)
sumdp[i][j][ii] = 0;
cin >> n;
for (int i = 1; i <= 2 * n + 1; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int s = 0; s <= 30 * n; s++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
if (h1 == 10)
{
for (int h2 = 0; h2 <= 10; h2++)
{
if (h2 == 10)
{
for (int h3 = 0; h3 <= 10; h3++)
{
if (h1 + h2 + h3 <= s and ok(h1,2 * n - 1,-1) and ok(h2,2 * n,-1) and ok(h3,2 * n + 1,-1) and okv(s,n))
dp[n][s][h1][h2][h1 + h2 + h3]++;
}
}
else
{
for (int h3 = 0; h3 <= 10 - h2; h3++)
{
if (h1 + h2 + h3 <= s and ok(h1,2 * n - 1,-1) and ok(h2,2 * n,-1) and ok(h3,2 * n + 1,h2) and okv(s,n))
dp[n][s][h1][h2][h1 + h2 + h3]++;
}
}
}
}
else
{
for (int h2 = 0; h2 <= 10 - h1; h2++)
{
if (h1 + h2 == 10 and ok(h1,2 * n - 1,-1) and ok(h2, 2 * n,h1))
{
for (int h3 = 0; h3 <= 10; h3++)
{
if (ok(h3,2 * n + 1,-1) and h1 + h2 + h3 <= s and okv(s,n))
dp[n][s][h1][h2][h1 + h2 + h3]++;
}
}
else if (h1 + h2 < 10)
{
if (h1 + h2 <= s and ok(h1,2 * n - 1,-1) and ok(h2,2 * n,h1) and ok(-1,2 * n + 1,-1) and okv(s,n))
dp[n][s][h1][h2][h1 + h2]++;
}
}
}
}
}
/*for (int i = n; i > 1; i--)
{
for (int s = 0; s <= 30 * i; s++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
for (int h2 = 0; h2 <= 10; h2++)
{
for (int vl = 0; vl <= min(30ll,s); vl++)
{
if (dp[i][s][h1][h2][vl] == 0)
continue;
if (!okv(s - vl,i - 1))
continue;
//cout << i << ' ' << s << ' ' << h1 << ' ' << h2 << ' ' << vl << endl;
for (int h1p = 0; h1p <= 10; h1p++)
{
for (int h2p = 0; h2p <= 10; h2p++)
{
if (f(h1p,h2p,h1,h2) <= s - vl)
{
if (h1p == 10 and ok(10,2 * i - 3,true,-1) and ok(-1,2 * i - 2,false,-1))
dp[i - 1][s - vl][h1p][h2p][f(h1p,h2p,h1,h2)] += dp[i][s][h1][h2][vl];
else if (h1p != 10)
{
if (h1p + h2p <= 10 and ok(h1p,2 * i - 3,false,-1) and ok(h2p,2 * i - 2,false,h1p))
dp[i - 1][s - vl][h1p][h2p][f(h1p,h2p,h1,h2)] += dp[i][s][h1][h2][vl];
}
}
}
}
}
}
}
}
}*/
for (int s = 0; s <= 30 * n; s++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
for (int h2 = 0; h2 <= 10; h2++)
{
for (int vl = 0; vl <= 30; vl++)
{
sumdp[n][s][vl] += dp[n][s][h1][h2][vl];
sdp[n][s][vl][h1] += dp[n][s][h1][h2][vl];
//if (dp[n][s][h1][h2][vl] != 0)
// cout << s << ' ' << h1 << ' ' << h2 << ' ' << vl << ' ' << dp[n][s][h1][h2][vl] << endl;
}
}
}
}
for (int i = n - 1; i >= 1; i--)
{
for (int s = 0; s <= 30 * i; s++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
for (int h2 = 0; h2 <= 10; h2++)
{
for (int vlp = 0; vlp <= 30; vlp++)
{
if (h1 == 10)
{
for (int h2p = 0; h2p <= 10; h2p++)
if (ok(h1,2 * i - 1,-1) and ok(-1,2 * i,-1))
dp[i][s][h1][h2][10 + h2 + h2p] += dp[i + 1][s + vlp][h2][h2p][vlp];
}
else if (h1 + h2 == 10)
{
for (int h1p = 0; h1p <= 10; h1p++)
if (ok(h1,2 * i - 1,-1) and ok(h2,2 * i,h1))
dp[i][s][h1][h2][10 + h1p] += sdp[i + 1][s + vlp][vlp][h1p];
}
else if (h1 + h2 < 10)
{
if (ok(h1,2 * i - 1,-1) and ok(h2,2 * i,h1))
dp[i][s][h1][h2][h1 + h2] += sumdp[i + 1][s + vlp][vlp];
}
}
}
}
}
for (int s = 0; s <= 30 * i; s++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
for (int h2 = 0; h2 <= 10; h2++)
{
for (int vl = 0; vl <= 30; vl++)
{
if (!okv(s,i))
dp[i][s][h1][h2][vl] = 0;
//if (dp[i][s][h1][h2][vl] != 0)
// cout << i << ' ' << s << ' ' << h1 << ' ' << h2 << ' ' << vl << ' ' << dp[i][s][h1][h2][vl] << endl;
sumdp[i][s][vl] += dp[i][s][h1][h2][vl];
sdp[i][s][vl][h1] += dp[i][s][h1][h2][vl];
}
}
}
}
}
int ans = 0;
for (int s = 0; s <= 30; s++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
for (int h2 = 0; h2 <= 10; h2++)
{
//if (dp[1][s][h1][h2][s] != 0)
//cout << s << ' ' << h1 << ' ' << h2 << ' ' << dp[1][s][h1][h2][s] << endl;
ans += dp[1][s][h1][h2][s];
}
}
}
cout << ans << '\n';
}
signed main()
{
int tc;
cin >> tc;
while (tc--)
testcase();
return 0;
}
/**
hoping for a miracle
**/
/*
1
2
?????
10 -1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
537 ms |
112580 KB |
Output is correct |
| 2 |
Correct |
576 ms |
112572 KB |
Output is correct |
| 3 |
Correct |
637 ms |
112464 KB |
Output is correct |
| 4 |
Correct |
670 ms |
112636 KB |
Output is correct |
| 5 |
Correct |
699 ms |
112472 KB |
Output is correct |
| 6 |
Correct |
790 ms |
112476 KB |
Output is correct |
| 7 |
Correct |
927 ms |
112476 KB |
Output is correct |
| 8 |
Correct |
817 ms |
112476 KB |
Output is correct |
| 9 |
Correct |
668 ms |
112476 KB |
Output is correct |
| 10 |
Correct |
817 ms |
112472 KB |
Output is correct |
| 11 |
Execution timed out |
1035 ms |
112728 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
819 ms |
112472 KB |
Output is correct |
| 2 |
Correct |
889 ms |
112672 KB |
Output is correct |
| 3 |
Correct |
789 ms |
112668 KB |
Output is correct |
| 4 |
Correct |
941 ms |
112668 KB |
Output is correct |
| 5 |
Correct |
990 ms |
112668 KB |
Output is correct |
| 6 |
Execution timed out |
1065 ms |
112948 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
429 ms |
112476 KB |
Output is correct |
| 2 |
Correct |
946 ms |
112476 KB |
Output is correct |
| 3 |
Correct |
799 ms |
112476 KB |
Output is correct |
| 4 |
Correct |
821 ms |
112476 KB |
Output is correct |
| 5 |
Correct |
751 ms |
112628 KB |
Output is correct |
| 6 |
Execution timed out |
1068 ms |
112476 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
962 ms |
112672 KB |
Output is correct |
| 2 |
Correct |
766 ms |
112688 KB |
Output is correct |
| 3 |
Correct |
951 ms |
112472 KB |
Output is correct |
| 4 |
Correct |
722 ms |
112476 KB |
Output is correct |
| 5 |
Correct |
766 ms |
112544 KB |
Output is correct |
| 6 |
Correct |
886 ms |
112668 KB |
Output is correct |
| 7 |
Correct |
799 ms |
112472 KB |
Output is correct |
| 8 |
Correct |
795 ms |
112672 KB |
Output is correct |
| 9 |
Correct |
840 ms |
112476 KB |
Output is correct |
| 10 |
Execution timed out |
1014 ms |
112472 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
537 ms |
112580 KB |
Output is correct |
| 2 |
Correct |
576 ms |
112572 KB |
Output is correct |
| 3 |
Correct |
637 ms |
112464 KB |
Output is correct |
| 4 |
Correct |
670 ms |
112636 KB |
Output is correct |
| 5 |
Correct |
699 ms |
112472 KB |
Output is correct |
| 6 |
Correct |
790 ms |
112476 KB |
Output is correct |
| 7 |
Correct |
927 ms |
112476 KB |
Output is correct |
| 8 |
Correct |
817 ms |
112476 KB |
Output is correct |
| 9 |
Correct |
668 ms |
112476 KB |
Output is correct |
| 10 |
Correct |
817 ms |
112472 KB |
Output is correct |
| 11 |
Execution timed out |
1035 ms |
112728 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
