#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
int dp[11][301][32][11][11];
int sdp[11][301][31][11],sumdp[11][301][31];
int n;
char a[25];
int v[15];
bool ok(int x,int pos,bool strike,int prec)
{
if (a[pos] == '?')
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])
return true;
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()
{
memset(dp,0,sizeof(dp));
memset(sdp,0,sizeof(sdp));
memset(sumdp,0,sizeof(sumdp));
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,true,-1) and ok(h2,2 * n,true,-1) and ok(h3,2 * n + 1,true,-1) and okv(s,n))
dp[n][s][h1 + h2 + h3][h1][h2]++;
}
}
else
{
for (int h3 = 0; h3 <= 10 - h2; h3++)
{
if (h1 + h2 + h3 <= s and ok(h1,2 * n - 1,true,-1) and ok(h2,2 * n,false,-1) and ok(h3,2 * n + 1,false,h2) and okv(s,n))
dp[n][s][h1 + h2 + h3][h1][h2]++;
}
}
}
}
else
{
for (int h2 = 0; h2 <= 10 - h1; h2++)
{
if (h1 + h2 == 10 and ok(h1,2 * n - 1,false,-1) and ok(h2, 2 * n,false,h1))
{
for (int h3 = 0; h3 <= 10; h3++)
{
if (ok(h3,2 * n + 1,true,-1) and h1 + h2 + h3 <= s and okv(s,n))
dp[n][s][h1 + h2 + h3][h1][h2]++;
}
}
else if (h1 + h2 < 10)
{
if (h1 + h2 <= s and ok(h1,2 * n - 1,false,-1) and ok(h2,2 * n,false,h1) and ok(-1,2 * n + 1,false,-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][vl][h1][h2];
sdp[n][s][vl][h1] += dp[n][s][vl][h1][h2];
//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 vlp = 0; vlp <= 30; vlp++)
{
for (int h1 = 0; h1 <= 10; h1++)
{
for (int h2 = 0; h2 <= 10; h2++)
{
if (h1 == 10)
{
for (int h2p = 0; h2p <= 10; h2p++)
if (ok(h1,2 * i - 1,true,-1) and ok(-1,2 * i,true,-1))
dp[i][s][10 + h2 + h2p][h1][h2] += dp[i + 1][s + vlp][vlp][h2][h2p];
}
else if (h1 + h2 == 10)
{
for (int h1p = 0; h1p <= 10; h1p++)
if (ok(h1,2 * i - 1,false,-1) and ok(h2,2 * i,false,h1))
dp[i][s][10 + h1p][h1][h2] += sdp[i + 1][s + vlp][vlp][h1p];
}
else if (h1 + h2 < 10)
{
if (ok(h1,2 * i - 1,false,-1) and ok(h2,2 * i,false,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][vl][h1][h2] = 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][vl][h1][h2];
sdp[i][s][vl][h1] += dp[i][s][vl][h1][h2];
}
}
}
}
}
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][s][h1][h2];
}
}
}
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 |
475 ms |
110164 KB |
Output is correct |
| 2 |
Correct |
489 ms |
110428 KB |
Output is correct |
| 3 |
Correct |
540 ms |
110424 KB |
Output is correct |
| 4 |
Correct |
575 ms |
110424 KB |
Output is correct |
| 5 |
Correct |
583 ms |
110428 KB |
Output is correct |
| 6 |
Correct |
684 ms |
110172 KB |
Output is correct |
| 7 |
Correct |
813 ms |
110168 KB |
Output is correct |
| 8 |
Correct |
668 ms |
110428 KB |
Output is correct |
| 9 |
Correct |
559 ms |
110168 KB |
Output is correct |
| 10 |
Correct |
681 ms |
110428 KB |
Output is correct |
| 11 |
Execution timed out |
1036 ms |
110168 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
536 ms |
110400 KB |
Output is correct |
| 2 |
Correct |
613 ms |
110400 KB |
Output is correct |
| 3 |
Correct |
586 ms |
110404 KB |
Output is correct |
| 4 |
Correct |
685 ms |
110172 KB |
Output is correct |
| 5 |
Correct |
703 ms |
110404 KB |
Output is correct |
| 6 |
Execution timed out |
1029 ms |
110228 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
326 ms |
110424 KB |
Output is correct |
| 2 |
Correct |
720 ms |
110172 KB |
Output is correct |
| 3 |
Correct |
620 ms |
110436 KB |
Output is correct |
| 4 |
Correct |
616 ms |
110428 KB |
Output is correct |
| 5 |
Correct |
607 ms |
110428 KB |
Output is correct |
| 6 |
Execution timed out |
1016 ms |
110168 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
676 ms |
110424 KB |
Output is correct |
| 2 |
Correct |
573 ms |
110168 KB |
Output is correct |
| 3 |
Correct |
692 ms |
110428 KB |
Output is correct |
| 4 |
Correct |
557 ms |
110172 KB |
Output is correct |
| 5 |
Correct |
584 ms |
110428 KB |
Output is correct |
| 6 |
Correct |
667 ms |
110428 KB |
Output is correct |
| 7 |
Correct |
592 ms |
110248 KB |
Output is correct |
| 8 |
Correct |
588 ms |
110424 KB |
Output is correct |
| 9 |
Correct |
600 ms |
110172 KB |
Output is correct |
| 10 |
Correct |
710 ms |
110168 KB |
Output is correct |
| 11 |
Correct |
671 ms |
110172 KB |
Output is correct |
| 12 |
Correct |
649 ms |
110172 KB |
Output is correct |
| 13 |
Correct |
613 ms |
110428 KB |
Output is correct |
| 14 |
Execution timed out |
1026 ms |
110404 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
475 ms |
110164 KB |
Output is correct |
| 2 |
Correct |
489 ms |
110428 KB |
Output is correct |
| 3 |
Correct |
540 ms |
110424 KB |
Output is correct |
| 4 |
Correct |
575 ms |
110424 KB |
Output is correct |
| 5 |
Correct |
583 ms |
110428 KB |
Output is correct |
| 6 |
Correct |
684 ms |
110172 KB |
Output is correct |
| 7 |
Correct |
813 ms |
110168 KB |
Output is correct |
| 8 |
Correct |
668 ms |
110428 KB |
Output is correct |
| 9 |
Correct |
559 ms |
110168 KB |
Output is correct |
| 10 |
Correct |
681 ms |
110428 KB |
Output is correct |
| 11 |
Execution timed out |
1036 ms |
110168 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
