Statistics

Problem Statement for "AnotherCoinProblem"

Problem Statement

The monetary system in Absurdistan is really simple and systematic. The locals only use coins. The coins come in different values. The values used are:

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000, ...

Formally, for each K>=0 there are coins worth 10K, and coins worth 25*100K.

You want to buy a new car. Its price is cost. Write a method that will return the smallest number of coins necessary to pay exactly the cost of the car (assuming you have a sufficient supply of coins of each of the types you will need).

Definition

Class:
AnotherCoinProblem
Method:
minimumCoins
Parameters:
long
Returns:
int
Method signature:
int minimumCoins(long cost)
(be sure your method is public)

Constraints

  • cost will be between 1 and 10^15, inclusive.

Examples

  1. 47

    Returns: 5

    The best way to pay 47 is 25+10+10+1+1.

  2. 9

    Returns: 9

    To pay 9, we can only use nine coins worth 1 each.

  3. 250111

    Returns: 4

  4. 25

    Returns: 1

  5. 1

    Returns: 1

  6. 24

    Returns: 6

  7. 30

    Returns: 3

  8. 31

    Returns: 4

  9. 32

    Returns: 5

  10. 33

    Returns: 6

  11. 34

    Returns: 7

  12. 35

    Returns: 2

  13. 36

    Returns: 3

  14. 37

    Returns: 4

  15. 38

    Returns: 5

  16. 39

    Returns: 6

  17. 40

    Returns: 4

  18. 41

    Returns: 5

  19. 42

    Returns: 6

  20. 43

    Returns: 7

  21. 44

    Returns: 8

  22. 45

    Returns: 3

  23. 76540123

    Returns: 16

    3*25,000,000 + 1*1,000,000 + 2*250,000 + 4*10,000 + 1*100 + 2*10 + 3*1 = 76,540,123 3 + 1 + 2 + 4 + 1 + 2 + 3 = 16

  24. 1000000000000000

    Returns: 1

  25. 987654321098765

    Returns: 50

  26. 101202727737

    Returns: 21

  27. 125908112010729

    Returns: 30

  28. 12786

    Returns: 9

  29. 137206159

    Returns: 19

  30. 138015088383

    Returns: 39

  31. 14740840019

    Returns: 29

  32. 149205

    Returns: 18

  33. 152555

    Returns: 11

  34. 154167205

    Returns: 25

  35. 160210158

    Returns: 15

  36. 16597166

    Returns: 26

  37. 1762101

    Returns: 9

  38. 179026314073902

    Returns: 36

  39. 18007238816

    Returns: 32

  40. 2

    Returns: 2

  41. 21

    Returns: 3

  42. 22162970668

    Returns: 31

  43. 222060

    Returns: 9

  44. 2231

    Returns: 8

  45. 22892429063

    Returns: 32

  46. 249388745191

    Returns: 40

  47. 27

    Returns: 3

  48. 271728800179794

    Returns: 45

  49. 2772788690199

    Returns: 36

  50. 280

    Returns: 7

  51. 284

    Returns: 11

  52. 32322717478489

    Returns: 43

  53. 348750

    Returns: 15

  54. 35227460790

    Returns: 27

  55. 370792930

    Returns: 22

  56. 3762407577745

    Returns: 34

  57. 37766739439818

    Returns: 45

  58. 3814983131119

    Returns: 40

  59. 3857

    Returns: 11

  60. 39384686844

    Returns: 45

  61. 394737

    Returns: 15

  62. 3966461843

    Returns: 32

  63. 4

    Returns: 4

  64. 4046

    Returns: 8

  65. 411581015298

    Returns: 30

  66. 445197216031

    Returns: 28

  67. 464729220

    Returns: 27

  68. 479244517

    Returns: 28

  69. 480

    Returns: 9

  70. 48695825605538

    Returns: 35

  71. 507326498628267

    Returns: 51

  72. 50910288302

    Returns: 29

  73. 530169

    Returns: 15

  74. 53239712070541

    Returns: 37

  75. 54428

    Returns: 17

  76. 580483816

    Returns: 28

  77. 581

    Returns: 11

  78. 58657906

    Returns: 25

  79. 606

    Returns: 12

  80. 6077000

    Returns: 17

  81. 60962067

    Returns: 18

  82. 6117781833

    Returns: 33

  83. 61212483

    Returns: 21

  84. 63303834486366

    Returns: 39

  85. 64

    Returns: 7

  86. 64168674663308

    Returns: 47

  87. 6654187395818

    Returns: 44

  88. 66674598532988

    Returns: 41

  89. 6707815093726

    Returns: 37

  90. 6831214819

    Returns: 31

  91. 6905736332

    Returns: 32

  92. 69510

    Returns: 12

  93. 703333398646249

    Returns: 49

  94. 706151903

    Returns: 32

  95. 721879

    Returns: 22

  96. 73180336290549

    Returns: 39

  97. 7386766142832

    Returns: 39

  98. 74016690

    Returns: 21

  99. 754873477324

    Returns: 34

  100. 755726100764

    Returns: 26

  101. 763585411389141

    Returns: 45

  102. 77463302859

    Returns: 36

  103. 78566

    Returns: 17

  104. 786003196119

    Returns: 36

  105. 8068732

    Returns: 25

  106. 81115217

    Returns: 20

  107. 818220

    Returns: 15

  108. 8189362163958

    Returns: 51

  109. 8212900

    Returns: 16

  110. 8318120

    Returns: 20

  111. 83789357745

    Returns: 30

  112. 84925531173

    Returns: 30

  113. 8501490251

    Returns: 17

  114. 89703603

    Returns: 18

  115. 90

    Returns: 6

  116. 904748

    Returns: 17

  117. 9133

    Returns: 13

  118. 924422482

    Returns: 34

  119. 933914256836079

    Returns: 51

  120. 9433

    Returns: 16

  121. 9599505285247

    Returns: 40

  122. 9713

    Returns: 11

  123. 979793479722000

    Returns: 45

  124. 999999999994799

    Returns: 68

  125. 999999999994798

    Returns: 67

  126. 300012200300000

    Returns: 11

  127. 3000000000

    Returns: 3

  128. 25000000000030

    Returns: 4

  129. 1082406931

    Returns: 25

  130. 10528479858031

    Returns: 34

  131. 3000

    Returns: 3

  132. 65

    Returns: 5

  133. 999999999999997

    Returns: 70

  134. 678886

    Returns: 19

  135. 30000000000000

    Returns: 3

  136. 250

    Returns: 4

  137. 666

    Returns: 12

  138. 9999

    Returns: 18

  139. 83000000000000

    Returns: 8

  140. 287345444

    Returns: 29

  141. 123455463457651

    Returns: 31

  142. 5436534643654

    Returns: 40

  143. 42523526623

    Returns: 25

  144. 94949494

    Returns: 40

  145. 55

    Returns: 4

  146. 784985601224794

    Returns: 49

  147. 1234567891011

    Returns: 27

  148. 131679235679767

    Returns: 43

  149. 994949494949494

    Returns: 79

  150. 750

    Returns: 9

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: