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

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

11560 - Fixing the Bugs

Post by wjomlex » Thu Jun 24, 2010 4:14 am

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 :D

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

Post by tjocko » Tue Oct 05, 2010 3:00 pm

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

Post by Silent_Coder » Fri Nov 21, 2014 7:17 pm

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

Post Reply

Return to “Volume 115 (11500-11599)”