## 11299 - Separating Rods

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

### 11299 - Separating Rods

I don't understand the problem statement. Can someone please explain it more clearly?

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:
We have a segment consisting from other segmest.
For example second test: 1 1 10
We have segmens of length 12 (1+1+10).
Now we can make K cut, however we can cut(divide) segment only in places where it is connected.
With one cut from the previous segment we can get only 2(1+1) + 10 or 1 + 11(1+10).

Now we must minimize the longest segment after K cuts, and found the number of ways to achieve this minimum.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Lomir wrote:We have a segment consisting from other segmest.
For example second test: 1 1 10
We have segmens of length 12 (1+1+10).
Now we can make K cut, however we can cut(divide) segment only in places where it is connected.
With one cut from the previous segment we can get only 2(1+1) + 10 or 1 + 11(1+10).

Now we must minimize the longest segment after K cuts, and found the number of ways to achieve this minimum.
What I don't get is why are there 2 ways of making the longest segment 10.
Nevermind, I now understand.

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm
You dont have to use K separations, the 2 ways are:

(1+1) (10) with 1 separation
(1)(1)(10) with 2 separations

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I got many WA on this problem because one of the judge input has n=0
In that case, the correct output is 0 1 which doesn't make sense.

Maybe the maximum element of an empty set is defined to be 0?

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am
In axiomatic set theory, the max of a set is defined to be the supremium
or sup of that set over all values that members of the set can take on.
Actually, the least upper bound (sup or supremum) of the empty set that is a subset of the integers, is negative infinity. However the range of the rods is from [0,+infinity), so it's 0 in this case. It's correct.

See proof below:

Code: Select all

``````
Let K be the miximum length of the rods,

Max({})=Sup({})=min( {0,+infinity} U {0,1,..,K} ) = 0.

``````