ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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;
}
Re: Problem 2094 was rejudged
Posted by pizdec 27 Jul 2018 12:01
If this code AC then delete him.