11560 - Fixing the Bugs

[wjomlex]

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]

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]

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