10509 - R U Kidding Mr. Feynman?

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Q10509 Help~~~

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!! :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

10509 - R U Kidding Mr. Feynman?

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... :o

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!!

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

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...
Istiaque Ahmed [the LA-Z-BOy]

Nak
New poster
Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

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]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Ok

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

yes, this is how u should approach.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

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. 8)

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

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

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! :-?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

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

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

Overlord
New poster
Posts: 4
Joined: Sun Jun 15, 2003 11:19 am

What about pascal?

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.
God is dead - Nietzsche
Nietzsche is dead - God

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Disputed

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Overlord
New poster
Posts: 4
Joined: Sun Jun 15, 2003 11:19 am

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.
God is dead - Nietzsche
Nietzsche is dead - God

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

10509 - R U Kidding Mr. Feynman?

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.
_____________
NO sigNature

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

I don't like the judge!

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!
There are 10 kind of people on this world: those who understand binary and those who don't!

Post Reply

Return to “Volume 105 (10500-10599)”