11236  Grocery store
Moderator: Board moderators
11236  Grocery store
Getting WA again & again.
Can anyone tell me exactly how many solutions are there in total?
My program prints only 907 solutions which i think is less than the actual number of solutions.
Can anyone tell me exactly how many solutions are there in total?
My program prints only 907 solutions which i think is less than the actual number of solutions.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11236  Grocery Store
Finally I've solved this problem.sunny wrote:Getting WA again & again.
Can anyone tell me exactly how many solutions are there in total?
My program prints only 907 solutions which i think is less than the actual number of solutions.
The number of the solutions is 949.
here is my code, i am getting only 667 solutions
Code: Select all
int main () {
long long a, b, c;
for (a = 1 ; 4 * a <= 2000; a ++)
for (b = a ; a + 3 * b <= 2000; b ++)
for (c = b ; a + b + 2 * c <= 2000; c ++)
{
long long p = (1.0 * a * b * c);
long long s = (0.0 + a + b + c);
if (p <= 1000000) continue;
long long d = (1000000 * s) / (p  1000000);
if ( d >= c && ( s +d ) <= 2000) {
double a1 = a/100.0;
double b1 = b/100.0;
double c1 = c/100.0;
double d1 = d/100.0;
double s1 = a1 + b1 + c1 + d1;
double p1 = a1 * b1 * c1 * d1;
if (s1 == p1) {
printf("%0.2lf %0.2lf %0.2lf %0.2lf\n", a/100.0, b/100.0, c/100.0, d/100.0);
}
}
}
}
i think precision issue.
change this line : if(s1==p1)
to,
or,
change this line : if(s1==p1)
to,
Code: Select all
if(fabs(s1p1)<1e9)
Code: Select all
if ((a+b+c+d)*1000000==a*b*c*d)

 Learning poster
 Posts: 60
 Joined: Sun Apr 16, 2006 7:59 pm

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, SUST
O(n^3) certainly get Time Limit Exceed. But not much time to crash a PC.
After running and print the solution you will see that:
Maximum value for a, b, c is 125, 592, 884.
So, the complexity of the algorithm reduces in O(max(a)*max(b)*max(c)).
Now, This will pass the TLE. Other, There is huge pruning in the loop that can make decision for finding a solution or not.
After running and print the solution you will see that:
Maximum value for a, b, c is 125, 592, 884.
So, the complexity of the algorithm reduces in O(max(a)*max(b)*max(c)).
Now, This will pass the TLE. Other, There is huge pruning in the loop that can make decision for finding a solution or not.