Page 1 of 3

11001 - Necklace

Posted: Wed Mar 08, 2006 1:06 pm
by boshkash1986
What does unique mean in this problem

Posted: Wed Mar 08, 2006 1:50 pm
by little joey
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.

Posted: Wed Mar 08, 2006 2:58 pm
by sumankar
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?

Posted: Wed Mar 08, 2006 3:23 pm
by little joey
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?

Posted: Wed Mar 08, 2006 3:52 pm
by sumankar
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 :(

Posted: Thu Mar 09, 2006 10:54 am
by boshkash1986
so please can anyone explain to me how the second sample input gives a zero at the output ?


Thanks alot

Posted: Thu Mar 09, 2006 11:32 am
by mf
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.

Posted: Thu Mar 09, 2006 11:51 am
by sclo
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.

Posted: Sat Mar 11, 2006 3:59 am
by Emilio
Hello there!
I'm getting WA. Could anyone say me why?
Sorry for post my code

Code: Select all

EDITED POST

Posted: Sat Mar 11, 2006 4:11 am
by mf
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.

Posted: Sat Mar 11, 2006 4:27 am
by Emilio
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

Posted: Sat Mar 11, 2006 4:52 am
by mf
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

Posted: Sat Mar 11, 2006 2:10 pm
by Emilio
Thanks mf!
I would must have read the problem more slowly.
I considered that case like a good case.

Posted: Tue Mar 28, 2006 6:10 pm
by billor9999
can anyone post the results of those test cases below:
40000 3
40000 9
50000 3
60000 7
60000 9
60000 11

Posted: Tue Mar 28, 2006 6:56 pm
by Darko
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