#include <iostream>
#include <fstream>
using namespace std;
const int nmax=12;
long long dp[nmax][300][12][12];
long long ans;
int val[100];
char ch1,ch2,ch,ch3;
int i,scor,i1,i2,j1,j2,t,n,sum,p1,p2,j,i3;
string s;
bool valid(int x,int y)
{
ch1=s[2*(i-1)];ch2=s[2*(i-1)+1];
if(x==10)
{
return (((ch1=='x')||(ch1=='?'))&&((ch2=='?'||ch2=='-')));
}
if(ch1=='x'||ch2=='-')
{
return (x==10);
}
bool bun=(ch1=='?'||ch1-'0'==x);
bun&=(x+y<10);
if(x+y==10)
{
return (bun&&(ch2=='/'||ch2=='?'));
}
if(ch2=='/')
{
return (((x+y)==10)&&bun);
}
bun&=(ch2=='?'||ch2-'0'==y);
return bun;
}
bool vezi3()
{
bool bun=1;
//return (i1==0&&i2==0&&i3==0);
if(i1+i2<10) bun&=(i3==0);
if(ch1>='0'&&ch1<='9')
{
bun&=(i1==ch1-'0');
}
if(ch2>='0'&&ch2<='9')
{
bun&=(i2==ch2-'0');
}
if(ch3>='0'&&ch3<='9')
{
bun&=(i3==ch3-'0');
}
return (i1+i2<10);
if(i1+i2<10) bun&=(ch3=='-'||ch3=='?');
if(i1==10&&ch2=='/') return 0;
if(i1==10&&i2+i3==10)
{
bun&=((ch3=='?'||ch3=='/'));
}
if(ch3=='/')
{
bun&=(i1==10&&i2+i3==10);
}
if(i1+i2>=10&&ch3=='-') return 0;
if(i1==10) bun&=(((ch1=='x')||(ch1=='?')));
if(i1!=10&&i1+i2==10) bun&=(ch2=='/'||ch2=='?');
return bun;
}
int cl(int i1,int i2,int i3)
{
int ret=i1+i2+i3;
if(i1+i2>=10) ret+=i3;
if(i2==10) ret+=i3;
return ret;
}
int main()
{
//freopen("data.in","r",stdin);
cin>>t;
for(int cnt=1;cnt<=t;cnt++)
{
cin>>n;
cin>>s;
for(i=1;i<=n;i++)
cin>>val[i];
sum=20*n+10;
ch=s[2*n];
ch1=s[2*n-2];ch2=s[2*n-1];ch3=s[2*n];
for(scor=0;scor<=sum;scor++)
for(i1=0;i1<=10;i1++)
for(i2=0;i2<=10;i2++)
for(i3=0;i3<=10;i3++)
if(vezi3())
{
if(scor-cl(i1,i2,i3)>=0&&(val[n]==-1||val[n]==scor)&&(val[n-1]==-1||val[n-1]==scor-cl(i1,i2,i3)))
{
dp[n][scor-cl(i1,i2,i3)][i1][i2]++;
}
}
for(i=n-1;i>=1;i--)
{
for(scor=0;scor<=sum;scor++)
for(i1=0;i1<=10;i1++)
for(i2=0;i2<=10-i1;i2++)
if(valid(i1,i2))
{
for(p1=0;p1<=10;p1++)
for(p2=0;p2<=10;p2++)
{
if(i1==10&&scor-10-p1-p2>=0)
{
dp[i][scor-10-p1-p2][i1][p1]+=dp[i+1][scor][p1][p2];
}
if(i1!=10&&i1+i2==10&&scor-10-p1>=0)
{
dp[i][scor-10-p1][i1][i2]+=dp[i+1][scor][p1][p2];
}
if(i1+i2!=10&&scor-i1-i2>=0)
{
dp[i][scor-i1-i2][i1][i2]+=dp[i+1][scor][p1][p2];
}
}
}
if(val[i-1]!=-1)
for(scor=0;scor<=sum;scor++)
if(scor!=val[i-1])
for(i1=0;i1<=10;i1++)
for(i2=0;i2<=10;i2++)
dp[i][scor][i1][i2]=0;
}
ans=0;
for(i1=0;i1<=10;i1++)
for(i2=0;i2<=10;i2++)
ans+=dp[1][0][i1][i2];
cout<<ans<<'\n';
for(i=1;i<=n+1;i++)
for(scor=0;scor<=sum;scor++)
for(i1=0;i1<=10;i1++)
for(i2=0;i2<=10;i2++)
dp[i][scor][i1][i2]=0;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
166 ms |
2944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
121 ms |
2944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
286 ms |
2944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
