11299 - Separating Rods

[sclo]

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

[Lomir]

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]

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]

You dont have to use K separations, the 2 ways are:

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

[sclo]

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]

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.