Statistics

Problem Statement for "Stick"

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:

  1. 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.
  2. 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).

Definition

Class:
Stick
Method:
pieces
Parameters:
int
Returns:
int
Method signature:
int pieces(int x)
(be sure your method is public)

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

  1. 32

    Returns: 1

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

  2. 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.

  3. 10

    Returns: 2

  4. 1

    Returns: 1

  5. 2

    Returns: 1

  6. 3

    Returns: 2

  7. 4

    Returns: 1

  8. 5

    Returns: 2

  9. 6

    Returns: 2

  10. 7

    Returns: 3

  11. 8

    Returns: 1

  12. 9

    Returns: 2

  13. 11

    Returns: 3

  14. 12

    Returns: 2

  15. 13

    Returns: 3

  16. 14

    Returns: 3

  17. 15

    Returns: 4

  18. 16

    Returns: 1

  19. 17

    Returns: 2

  20. 18

    Returns: 2

  21. 19

    Returns: 3

  22. 20

    Returns: 2

  23. 21

    Returns: 3

  24. 22

    Returns: 3

  25. 23

    Returns: 4

  26. 24

    Returns: 2

  27. 25

    Returns: 3

  28. 26

    Returns: 3

  29. 27

    Returns: 4

  30. 28

    Returns: 3

  31. 29

    Returns: 4

  32. 30

    Returns: 4

  33. 31

    Returns: 5

  34. 33

    Returns: 2

  35. 34

    Returns: 2

  36. 35

    Returns: 3

  37. 36

    Returns: 2

  38. 37

    Returns: 3

  39. 38

    Returns: 3

  40. 39

    Returns: 4

  41. 40

    Returns: 2

  42. 41

    Returns: 3

  43. 42

    Returns: 3

  44. 43

    Returns: 4

  45. 44

    Returns: 3

  46. 45

    Returns: 4

  47. 46

    Returns: 4

  48. 47

    Returns: 5

  49. 49

    Returns: 3

  50. 50

    Returns: 3

  51. 51

    Returns: 4

  52. 52

    Returns: 3

  53. 53

    Returns: 4

  54. 54

    Returns: 4

  55. 55

    Returns: 5

  56. 56

    Returns: 3

  57. 57

    Returns: 4

  58. 58

    Returns: 4

  59. 59

    Returns: 5

  60. 60

    Returns: 4

  61. 61

    Returns: 5

  62. 62

    Returns: 5

  63. 63

    Returns: 6

  64. 64

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: