 # DUMPLING: Getting wa

hey I m having a prob in d problem-http://www.codechef.com/APRIL12/problems/DUMPLING
Here is my code- http://www.codechef.com/viewsolution/983332
The hcf and lcm functions as well as d algo is correct. It seems that the order in which i am doing d calculations is leading me to a wrong answer.
When i do this, it gets a right answer-

``````while(t--)
{
scanf("%llu %llu %llu %llu %llu",&a,&b,&c,&d,&k);
h1=hcf(a,b);
h2=hcf(c,d);
h3=hcf(gcd1,gcd2);
l=k*h3;
l/=h1;
l/=h2;
printf("%llu\n",l*2+1); //since k=0 is always a solution a to left, a to right
}
``````

But this causes a wrong answer-

`````` while(t--)
{
scanf("%llu %llu %llu %llu %llu",&a,&b,&c,&d,&k);
l=lcm(hcf(a,b),hcf(c,d));  //lcm as defined in above url
printf("%llu\n",(k/l)*2+1); //since k=0 is always a solution a to left, a to right
}
``````

Why is this happening cos they both essentially lead to the same expression

When we run the code for 1 10^18 10^18 10^18 10^18 10^18 (the worst case) …

here is what happens… when u calculate lcm. as u know LCM(a,b)=a*b/gcd(a,b);

a*b = 10^36. but c or c++ supports only to 10^18 (OVERFLOW CASE)…

so u have to optmize ur solution to do that…

2 Likes

hey thanks!!!

my pleasure !!! //