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

What does unique mean in this problem
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
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
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:
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:
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
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:
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
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:
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
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
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
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