10509 - R U Kidding Mr. Feynman?

Observer · Post by **Observer** » Sat Jun 14, 2003 5:37 am

* Sorry, since there's no forum for Vol CV, I'll just post it here *

Excuse me, I'm always getting WA in this qq.

So can anyone help me? Or have I misinterpreted the qq??

Should I try to expand (a + dx)^3 and just ignore the dx^2 and dx^3 terms? Or am I wrong? Plz tell!!

Some critical inputs/outputs would be nice too!!

Tobbi · Post by **Tobbi** » Sat Jun 14, 2003 7:18 am

This problem really bothers me!! I didn't solve it during the contest and I still don't get it accepted. And it shouldn't be complicated, though...

Isn't it just

Code: Select all

a = floor(sqrt3(n));
return a+(n-a^3)/(3*a^2);

I tried around with different roundings... However, nothing helped.

I get exactly the sample outputs, so may someone publish some other test cases please?? Thanks a ton!!

the LA-Z-BOy · Post by **the LA-Z-BOy** » Sat Jun 14, 2003 8:58 am

here's a tip from my team mate:
use double instead of long double.
you might get ac, tell us if you still got problem.
Greetings...

Nak · Post by **Nak** » Sat Jun 14, 2003 10:38 am

That's the same formula i used and got AC. I calculated a as:

[cpp]
double a = floor(pow(cube, 1.0/3.0)+0.0000000001);
[/cpp]

shamim · Post by **shamim** » Sat Jun 14, 2003 12:20 pm

yes, this is how u should approach.

Observer · Post by **Observer** » Sat Jun 14, 2003 4:46 pm

Possibly precision error when calculating dx...

I'm sure I've got the exact integral value of a.

So, any help?? Thx in advance!

Noim · Post by **Noim** » Sat Jun 14, 2003 6:40 pm

yes the LA-Z-BOy you are right.

During the contest , using long double i got WA. But when i use double instead of long double i then got AC.

Can you tell me , where to use double and where to long double?

Tobbi · Post by **Tobbi** » Sat Jun 14, 2003 11:54 pm

Yeah, thanks!! That's it! Now I got AC.
Nevertheless quite a mad judge, which imposes one using double instead of long double!

shamim · Post by **shamim** » Sun Jun 15, 2003 8:00 am

Post ur code. then i will be able to find any bug.

Overlord · Post by **Overlord** » Sun Jun 15, 2003 11:23 am

I tried to solve the problem using double in Pascal with the same formula. I got WA. Any hints? For cubic root i used trunc(exp((1/3)*ln(n))). A tried with int instead of trunc, too. Help please.

shamim · Post by **shamim** » Sun Jun 15, 2003 2:13 pm

This problem is definitely disputed.

from initial eq. n^1/3=a+dx

we get, n=a^3 + 3a^2(dx)+3a(dx)^2+ (dx)^3

here we should ingnore 3a(dx)^2 AND (dx)^3,

one thing that bothers me is why is it valid to ignore 3a(dx)^2,

there is a leading coefficient of 3a, it is numerically invalid to ignore this term. I think the judge should have considered that.

Observer · Post by **Observer** » Sun Jun 15, 2003 3:54 pm

Thx! By writing my code again, I've got an ACC finally... However, I still don't understand why I got WA before...

Overlord · Post by **Overlord** » Sun Jun 15, 2003 8:20 pm

This problem askes you to calculate the cubic root USING THE EXPLAINED approxximation method. It is valid to ignore (dx)^2, because the dr. did it, when calculating. On the other hand i don't understand what happened to the judge program not accepting solutions with long double. Anyone using Pascal please post his solution, because i don't have a clue how can it be solved to be accepted. That gave me nerves during the contest. You can see my solution two posts above.

Farid Ahmadov · Post by **Farid Ahmadov** » Tue Jun 17, 2003 10:15 am

Hello.
I get WA.
I use the formula
n=a^3+3*a^2*dx+3*a*dx^2+dx^3
I ignore dx^3.
Then
n-a^3=3*a*(a*dx+dx^2)
(n-a^3)/(3*a)=a*dx+dx^2
I ignore dx^2 here too
and at last I get
(n-a^3)/(3*a^2)=dx

Is it wrong or right. And why do I get WA?

Thanks.

Pier · Post by **Pier** » Tue Jun 17, 2003 8:41 pm

This is stupid!

If I use:
[pascal] writeln(output,(a+dx):0:4);[/pascal]

I get WA, but if I use

[pascal] a:= a+dx;
writeln(output,a:0:4);[/pascal]

I get AC!

OJ Board