11236 - Grocery store

All about problems in Volume 112. 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
sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

11236 - Grocery store

Post by sunny »

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.
Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11236 - Grocery Store

Post by Robert Gerbicz »

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.
Finally I've solved this problem.
The number of the solutions is 949.
sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

finally,got AC.

I missed 42 solutions because i didnt check the solutions where the numbers can be equal.
pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad »

Any hint please ?
sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

try to derive a O(n^3) solution from the equation: a+b+c+d=a*b*c*d
pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad »

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);
	          }
           }
}
}
sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

i think precision issue.
change this line : if(s1==p1)

to,

Code: Select all

if(fabs(s1-p1)<1e-9) 
or,

Code: Select all

if ((a+b+c+d)*1000000==a*b*c*d)
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

how is O(n^3) going to pass the time limit?
ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi »

>>sclo

here it is not exactly 2000^3
optimization is possible because a<=b<=c<=d.
and (a+b+c+d) <= 2000
Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_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.
Post Reply

Return to “Volume 112 (11200-11299)”