Stick

SRM 409 · 2008-07-10 · by slex

SRM 409 · 2008-07-10 · by slex · Simple Math, Simulation

Show categories

Class Name: Stick

Return Type: int

Method Name: pieces

Arg Types: (int)

Problem Statement

Little Johnny has a stick that is 64 centimeters long, but he thinks it would be more fun to play with a stick that is x centimeters long. He decides to break the original stick into a number of smaller sticks, and then glue them together to get a stick that is exactly x centimeters long.

The easiest way to break a stick is to break it in half, so Johnny will use the following procedure:

Sum the lengths of all the sticks (initially, there is just one 64 centimeter stick). While this sum is greater than x, repeat the following:
- Take one of the sticks with the shortest length and break it in half.
- If discarding one of the halves would not make the sum of the remaining sticks' lengths less than x, throw that half away.
Finally, glue the remaining sticks together to form a stick that is x centimeters long.

Return the number of sticks Johnny would have to glue together in the final step if he follows the above procedure. If he has only one stick when he gets to the final step, return 1 (see example 0).

Notes

The algorithm described in the problem statement guarantees that you will always end up with a total length of exactly x in the final step.

Constraints

x will be between 1 and 64, inclusive.

Examples

32
Returns: 1

After the first break Johnny gets a stick 32cm long.

48
Returns: 2

First, he breaks the stick into two 32cm long sticks. Then, he breaks one of the 32cm sticks in half and discards one of the halves. The remaining two sticks have a total length of 48cm when glued together.

10
Returns: 2

1
Returns: 1

2
Returns: 1

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Stick with a public method int pieces(int x) · 64 test cases · 2 s / 256 MB per case