ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2094. Thousand Imps

Problem 2094 was rejudged
Error in jury solution was fixed, all test answers updated, few new tests added. Most authors lost their AC.
Big thanks to the Winger for pointing out an issue and helping with fixing it.
Re: Problem 2094 was rejudged
Posted by Shen Yang 5 Oct 2017 19:28
What error was fixed,maybe my code has the same error??
Re: Problem 2094 was rejudged
Posted by Shen Yang 6 Oct 2017 14:35
oh yeah Accepted.. with guess,and
Re: Problem 2094 was rejudged
Posted by Shen Yang 6 Oct 2017 14:36
code::


#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
long double mi[2][1001][1001];
int n,a[2],b[2],pm;
long double pro,c[1001][1001],ex[2][1001],pr[1001][1001];
char str[1011];
int main()
{
    scanf("%d%d",&n,&pm);
    scanf("%s",str);
    pro=pm/100.;
    int i,j,s,p,q,cc=0,id;
    for(i=0;i<=n;i++)
      for(j=0;j<=i;j++)
      {
            if(j==0||j==i)
               c[i][j]=1;
          else
             c[i][j]=(c[i-1][j-1]+c[i-1][j]);
       }
    for(i=0;i<=n;i++)
    {
        if(i==0)
           ex[0][i]=ex[1][i]=1;
         else
         {
             ex[0][i]=ex[0][i-1]*pro;
             ex[1][i]=ex[1][i-1]*(1-pro);
        }
    }
    a[0]=a[1]=0;
    for(i=0;i<n;i++)
    {
        if(str[i]=='2')
        {
            id=i;
            cc++;
        }
        else if(str[i]=='1')
            a[cc]++;
    }
    int aa,bb,i1,c1,j1,c2;
    aa=id-a[0];
    bb=n-1-id-a[1];
    for(i1=aa;i1>=0;i1--)
       for(j1=bb;j1>=0;j1--)
       {
              pr[i1][j1]=c[aa][i1]*c[bb][j1]*ex[0][aa+bb-i1-j1]+(pr[i1+1][j1]*(i1+1)+pr[i1][j1+1]*(j1+1))*(1-pro)/(i1+j1+1);
          long double proe,qroe;
           proe=pr[i1+1][j1]*(1-pro)*(i1+1)/(i1+j1+1)/pr[i1][j1];
           qroe=pr[i1][j1+1]*(1-pro)*(j1+1)/(i1+j1+1)/pr[i1][j1];
           mi[1][i1][j1]=proe*mi[1][i1+1][j1]+qroe*(mi[1][i1][j1+1]+1);
           mi[0][i1][j1]=min(mi[1][i1][j1],proe*(mi[0][i1+1][j1]+1)+qroe*mi[0][i1][j1+1]);
      }
    printf("%.20f\n",(double)mi[0][0][0]+a[0]);
    return 0;
}