이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[11][301][11][11][32];
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()
{
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;
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][h1 + h2 + h3]++;
}
}
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][h1 + h2 + h3]++;
}
}
}
}
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][h1 + h2 + h3]++;
}
}
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];
}
}
}
}
}
}
}
}
}
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 |
---|
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... |