11001 - Necklace

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

What does unique mean in this problem

little joey · 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.

sumankar · 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?

little joey · 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?

sumankar · 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 · 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 · 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 · 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 · 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

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

Here are some tests:

Code: Select all

Code: Select all

btw, it's possible to solve this problem without floating point computations.

Emilio · 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

mf · 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 · 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 · 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 · Post by **Darko** » Tue Mar 28, 2006 6:56 pm

for the input:

Code: Select all

output:

Code: Select all

Darko