oj.uz

Submission #106201

# Submission time Handle Problem Language Result Execution time Memory
106201 2019-04-17T09:29:05 Z Bodo171 Bowling (BOI15_bow) C++14
0 / 100
 256 ms 3072 KB 
#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;
int i,scor,i1,i2,j1,j2,t,n,sum,p1,p2,j;
string s;
bool valid(int x,int y)
{
    ch1=s[2*(i-1)];ch2=s[2*(i-1)+1];
    //vezi caz cu ultimul spare
    if(x+y==10) return 0;//asta se sterge
    if(i==n&&x+y==10&&ch=='-') return 0;
    if(x==10)
    {
        return (((ch1=='x')||(ch1=='?'))&&((ch2=='?'||ch2=='-')));
    }
    if(ch1=='x'||ch2=='-')
    {
        return (x==10);
    }
    bool bun=(ch1=='?'||ch1-'0'==x);
    if(x+y==10)
    {
        return (bun&&(ch2=='/'||ch2=='?'));
    }
    if(ch2=='/')
    {
        return (((x+y)==10)&&bun);
    }
    bun&=(ch2=='?'||ch2-'0'==y);
    return bun;
}
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];
        if(ch=='?')
        {
            for(scor=0;scor<=sum;scor++)
                for(i1=0;i1<=9;i1++)//modifica la 10
                    if(scor+i1==val[n]||val[n]==-1)
                        dp[n+1][scor][i1][0]=1;
        }
        else
        {
            int num=0;
            if(ch=='x') num=10;
            else num=ch-'0';
            if(ch=='-') num=0;
            for(scor=0;scor<=sum;scor++)
                if(scor+num==val[n]||val[n]==-1)
                dp[n+1][scor][num][0]=1;
        }
        for(i=n;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;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 2936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 3072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 256 ms 2936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 2936 KB Output isn't correct
2 Halted 0 ms 0 KB -