11001 - Necklace

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

Moderator: Board moderators

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

11001 - Necklace

Post by boshkash1986 » Wed Mar 08, 2006 1:06 pm

What does unique mean in this problem

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 08, 2006 1:50 pm

If you have Vtotal=6 and V0=2, you can either make one disk with diameter 0.3*sqrt(6-2) = 0.6, or two disks with diameter 0.3*sqrt(3-2) = 0.3. Both necklaces have the same length (0.6) and therefor the answer is not unique.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 08, 2006 2:58 pm

Need help! This is what I tried:

Code: Select all

 
[1] L = n * D = 0.3 * n * sqrt( Vtot/n - V0 )
[2] L' = 0 && L'' < 0 or so on ...
What am I missing?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 08, 2006 3:23 pm

Nothing much, I think. The function L(n) is well behaved and has real values between it's two zeros n=0 and n=Vtot/Vo, and one maximum, so there is no need to consider the second derivative. Are you sure you don't report a value outside this range where L(n) becomes imaginary?
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 08, 2006 3:52 pm

Thanks!
little joey wrote:... Are you sure you don't report a value outside this range where L(n) becomes imaginary?
Well, I no longer have a way to check it, off-hand. I was so pissed off with
having a WA with this one, I well ... trashed the 20-odd lines. ;)
Hope my previous post isn't a spoiler. Realized it only now :(

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » Thu Mar 09, 2006 10:54 am

so please can anyone explain to me how the second sample input gives a zero at the output ?


Thanks alot

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Mar 09, 2006 11:32 am

In sample case #2, if you either take n=2 or n=3, you'll make a necklace of length 2*0.3*sqrt(10/2-2) = 3*0.3*sqrt(10/3-2) ~= 1.039. That's maximum possible, and since choice of n is not unique you are to print 0.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Mar 09, 2006 11:51 am

It is interesting to note that we don't need to know the total length to solve this problem. It is sufficient to compare the two candidate values of n and checking certain conditions.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Mar 11, 2006 3:59 am

Hello there!
I'm getting WA. Could anyone say me why?
Sorry for post my code

Code: Select all

EDITED POST
Last edited by Emilio on Sat Mar 11, 2006 4:28 am, edited 2 times in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Mar 11, 2006 4:11 am

Here are some tests:

Code: Select all

10 4
10 5
100 50
100 51
60000 600
60000 500
60000 300
42424 543
0 0

Code: Select all

1
1
1
1
50
60
100
39
btw, it's possible to solve this problem without floating point computations.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Mar 11, 2006 4:27 am

thanks for your test cases, I have maked some changes and now get correct answer for your test cases but continue getting WA.
Here is my new code (sorry for posting)

Code: Select all

CUT OFF
Where is my mistake please?
btw, I will try figure out how solve this problem without floating point computations
Last edited by Emilio on Sat Mar 11, 2006 2:11 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Mar 11, 2006 4:52 am

Output for cases, in which Vtotal = V0 should be 0.

Your program prints 1, and that's wrong according to this:
When V <= V0, no ceramic discs can be made

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Mar 11, 2006 2:10 pm

Thanks mf!
I would must have read the problem more slowly.
I considered that case like a good case.

billor9999
New poster
Posts: 1
Joined: Tue Mar 28, 2006 6:06 pm

Post by billor9999 » Tue Mar 28, 2006 6:10 pm

can anyone post the results of those test cases below:
40000 3
40000 9
50000 3
60000 7
60000 9
60000 11

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Mar 28, 2006 6:56 pm

for the input:

Code: Select all

40000 3 
40000 9 
50000 3 
60000 7 
60000 9 
60000 11
0 0
output:

Code: Select all

6667
2222
8333
4286
3333
2727
Darko

Post Reply

Return to “Volume 110 (11000-11099)”