### 11001 - Necklace

Posted:

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

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=33&t=10107

Page **1** of **3**

Posted: **Wed Mar 08, 2006 1:06 pm**

What does unique mean in this problem

Posted: **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.

Posted: **Wed Mar 08, 2006 2:58 pm**

Need help! This is what I tried:
What am I missing?

Code: Select all

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

Posted: **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?

Posted: **Wed Mar 08, 2006 3:52 pm**

Thanks!

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

Well, I no longer have a way to check it, off-hand. I was so pissed off withlittle joey wrote:... Are you sure you don't report a value outside this range where L(n) becomes imaginary?

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

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

Thanks alot

Thanks alot

Posted: **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.

Posted: **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.

Posted: **Sat Mar 11, 2006 3:59 am**

Hello there!

I'm getting WA. Could anyone say me why?

Sorry for post my code

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

Here are some tests:
btw, it's possible to solve this problem without floating point computations.

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

Posted: **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)
Where is my mistake please?

btw, I will try figure out how solve this problem without floating point computations

Here is my new code (sorry for posting)

Code: Select all

```
CUT OFF
```

btw, I will try figure out how solve this problem without floating point computations

Posted: **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:

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

Thanks mf!

I would must have read the problem more slowly.

I considered that case like a good case.

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

can anyone post the results of those test cases below:

40000 3

40000 9

50000 3

60000 7

60000 9

60000 11

40000 3

40000 9

50000 3

60000 7

60000 9

60000 11

Posted: **Tue Mar 28, 2006 6:56 pm**

for the input:
output:
Darko

Code: Select all

```
40000 3
40000 9
50000 3
60000 7
60000 9
60000 11
0 0
```

Code: Select all

```
6667
2222
8333
4286
3333
2727
```