Statistics

Problem Statement for "NewMoneySystem"

Problem Statement

You are creating the money system for a new game. The requirements are as follows:

  1. There will be exactly K different banknote values.
  2. The value of the smallest banknote will be equal to one dollar.
  3. The value of the i-th banknote will be equal to the value of the (i-1)-th banknote multiplied by 2, 3, 4 or 5.

The initial capital of a player will be N dollars, so you want to choose banknote values in such a way that minimizes the number of banknotes required to make N dollars. Assume that you have an infinite supply of banknotes for each value.

You will be given two integers N and K. Due to technical reasons, N will be given as a String with no leading zeros. Return the minimal number of banknotes required to make exactly N dollars. Note that you must minimize the number of actual banknotes, not the number of banknote values (see examples).

Definition

Class:
NewMoneySystem
Method:
chooseBanknotes
Parameters:
String, int
Returns:
long
Method signature:
long chooseBanknotes(String N, int K)
(be sure your method is public)

Constraints

  • N will be an integer between 1 and 1018, inclusive, with no leading zeros.
  • K will be between 1 and 100, inclusive.

Examples

  1. "1025"

    6

    Returns: 2

    The best set of banknote values is {1, 4, 16, 64, 256, 1024}. 1025 = 1024 + 1.

  2. "1005"

    5

    Returns: 3

    The best set of banknote values is {1, 5, 25, 100, 500}. 1005 = 2 * 500 + 5.

  3. "12000"

    14

    Returns: 1

  4. "924323565426323626"

    1

    Returns: 924323565426323626

    The answer can be rather big.

  5. "924323565426323626"

    50

    Returns: 10

  6. "1000000000000000000"

    1

    Returns: 1000000000000000000

  7. "1000000000000000000"

    36

    Returns: 1

  8. "1000000000000000000"

    34

    Returns: 1

  9. "1"

    1

    Returns: 1

  10. "1"

    100

    Returns: 1

  11. "7"

    100

    Returns: 2

  12. "1000000000000000000"

    100

    Returns: 1

  13. "59"

    3

    Returns: 7

  14. "3599"

    6

    Returns: 10

  15. "215999"

    9

    Returns: 16

  16. "12959999"

    12

    Returns: 17

  17. "777599999"

    15

    Returns: 23

  18. "46655999999"

    18

    Returns: 27

  19. "2799359999999"

    21

    Returns: 33

  20. "167961599999999"

    24

    Returns: 33

  21. "10077695999999999"

    27

    Returns: 38

  22. "604661759999999999"

    30

    Returns: 41

  23. "192432261334"

    40

    Returns: 8

  24. "19332614"

    31

    Returns: 6

  25. "246277938566864"

    47

    Returns: 11

  26. "26642438275453"

    27

    Returns: 11

  27. "927"

    11

    Returns: 3

  28. "38136235793326225"

    38

    Returns: 9

  29. "953"

    41

    Returns: 4

  30. "78"

    2

    Returns: 18

  31. "4"

    32

    Returns: 1

  32. "3"

    14

    Returns: 1

  33. "35344892846146"

    36

    Returns: 10

  34. "72546"

    9

    Returns: 5

  35. "866228215766"

    46

    Returns: 9

  36. "342975954184"

    19

    Returns: 12

  37. "181849565356"

    16

    Returns: 29

  38. "25326627334245"

    39

    Returns: 7

  39. "2458673655"

    1

    Returns: 2458673655

  40. "528941196"

    41

    Returns: 5

  41. "57712125"

    18

    Returns: 4

  42. "71275313"

    20

    Returns: 7

  43. "345532372883739"

    10

    Returns: 176912603

  44. "54949236439551957"

    41

    Returns: 10

  45. "5"

    48

    Returns: 1

  46. "37576"

    35

    Returns: 3

  47. "561173151851879"

    36

    Returns: 12

  48. "954246215119"

    22

    Returns: 11

  49. "85225966526744"

    21

    Returns: 21

  50. "26163"

    36

    Returns: 3

  51. "629285663"

    27

    Returns: 8

  52. "993556"

    33

    Returns: 5

  53. "123241977579112491"

    43

    Returns: 11

  54. "474676931998777871"

    26

    Returns: 36

  55. "66899777555156549"

    41

    Returns: 10

  56. "597178975547595112"

    30

    Returns: 16

  57. "574777873587886"

    35

    Returns: 12

  58. "889891776722159"

    25

    Returns: 18

  59. "919973122798829287"

    43

    Returns: 15

  60. "369527117423652"

    24

    Returns: 9

  61. "522353413731666175"

    14

    Returns: 427911935

  62. "895638226688675"

    5

    Returns: 1433021162707

  63. "762315356886997418"

    18

    Returns: 999218

  64. "13214373879396797"

    43

    Returns: 14

  65. "71959946744918637"

    31

    Returns: 11

  66. "86891948369876633"

    42

    Returns: 12

  67. "6629716148522132"

    26

    Returns: 14

  68. "52716887793411475"

    21

    Returns: 587

  69. "121934885619594972"

    38

    Returns: 10

  70. "943412933414453851"

    16

    Returns: 30913767

  71. "817543138393458831"

    32

    Returns: 14

  72. "914346125918722863"

    20

    Returns: 47979

  73. "195955923836882"

    22

    Returns: 20

  74. "84911522964686354"

    17

    Returns: 556514

  75. "4869439183774943"

    17

    Returns: 31951

  76. "939144231842438"

    19

    Returns: 294

  77. "33987261141554932"

    32

    Returns: 11

  78. "382772194686274765"

    40

    Returns: 10

  79. "554865247818621665"

    27

    Returns: 26

  80. "5567349627783654"

    10

    Returns: 2850483026

  81. "89855378478355687"

    40

    Returns: 11

  82. "51689449692452925"

    4

    Returns: 413515597539625

  83. "1005"

    5

    Returns: 3

  84. "924323565426323623"

    50

    Returns: 13

  85. "924325426323626"

    1

    Returns: 924325426323626

  86. "989898979698989898"

    99

    Returns: 13

  87. "99979999999999999"

    21

    Returns: 1115

  88. "924323565426323623"

    49

    Returns: 13

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: