## 11560 - Fixing the Bugs

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

### 11560 - Fixing the Bugs

I've tested this against over 2000 randomly generated test cases using uvatoolkit.com, and my answers are digit-for-digit exactly the same, but I still get WA.

Any ideas would be great

Code: Select all

``````
#include <stdio.h>

int b;
int t;
double f;
double a[1024][101][101];
double p[10];
int s[10];
int fails[10];

double dp(int mask, int fail, int time)
{
if(mask == (1 << b) - 1) //All done!
return 0;

if(a[mask][fail][time] != -1) //Already computed!
return a[mask][fail][time];

if(time == 0) //No time left!
return 0;

int bug = 0;
double exp = 0;
double psucc = 0;

for(int i=0;i < b;i++)
{
if(p[i]*s[i] > exp && (mask & (1 << i)) == 0)
{
psucc = p[i];
exp = p[i]*s[i];
bug = i;
}
}

double rtn = 0;

//On success...
rtn += psucc * (s[bug] + dp(mask | (1 << bug), fail - fails[bug], time - 1));

//On failure...
//Mark
p[bug] *= f;
fails[bug]++;

//Recurse
rtn += (1-psucc) * dp(mask, fail+1, time - 1);

//Unmark
p[bug] = psucc;
fails[bug]--;

a[mask][fail][time] = rtn;
return rtn;
}

int main()
{
while(scanf("%d %d %lf", &b, &t, &f) != EOF)
{
for(int i=0;i < b;i++)
{
scanf("%lf %d", p + i, s + i);
fails[i] = 0;
}

for(int i=0;i < (1 << b);i++)
for(int j=0;j <= t;j++)
for(int k=0;k <= t;k++)
a[i][j][k] = -1;

printf("%lf\n", dp(0, 0, t));
}
}

``````

tjocko
New poster
Posts: 7
Joined: Fri May 21, 2010 6:07 pm

### Re: 11560 - Fixing The Bugs

Here are some usable test cases and output from my (AC) solution. I have tried to cover all border cases with test suit.

A note on the output formatting - I use 7 decimals just to be
certain it comply with 10^-6 absolute accuracy rule.

Input:

Code: Select all

``````1 2 0.950000
0.700000 50
2 2 0.500000
0.750000 100
0.750000 20
6 100 0.5
0.5 100
0.5 100
0.5 100
0.5 100
0.5 100
0.5 100
0 10 0.5
1 0 0.5
0.5 10
1 10 0
0.5 10
1 10 1
0.5 10
1 10 0.5
0 10
1 10 0.5
1 10
1 10 0.5
0.5 0
1 10 0.5
0.5 10000
2 1 0.54
0.1 5055
0.67 4799
2 2 0.54
0.1 5055
0.67 4799
2 3 0.54
0.1 5055
0.67 4799
7 6 0.65
0.16 2130
0.97 7223
0.01 4679
0.43 8584
0.4 9785
0.92 6526
0.68 7444
10 100 0.7777777777777777777
0.7777777777777777 10000
0.666666666666 10000
0.55555555 10000
0.1111111111111 10000
0.22222222222 10000
0.3333333333333333 10000
0.44444444 10000
0.888888888888 10000
0.999999999999 10000
0.9 6548
``````
My code gives this output:

Code: Select all

``````44.9750000
95.6250000
426.7271329
0.0000000
0.0000000
5.0000000
9.9902344
0.0000000
10.0000000
0.0000000
7109.2970158
3215.3300000
4126.9868060
4549.4035106
28350.6552063
83524.4514778
``````

Silent_Coder
New poster
Posts: 1
Joined: Fri Nov 21, 2014 7:14 pm

### Re: 11560 - Fixing the Bugs

I got wa while printing 8 digits after decimal value, whereas printing 7 digits after decimal value gave me AC.