Statistics

Problem Statement for "AmountApproximation"

Problem Statement

We must pay D dollars. Unfortunately, we only have bills of two denominations: p1 dollars and p2 dollars. So, we want to overpay as little as possible.

You will be given ints D, p1 and p2. Return the minimum number of dollars greater than or equal to D that can be paid with the given bills. Assume that we have an infinite supply of both p1 and p2 dollar bills.

Definition

Class:
AmountApproximation
Method:
approximate
Parameters:
int, int, int
Returns:
int
Method signature:
int approximate(int D, int p1, int p2)
(be sure your method is public)

Constraints

  • D will be between 1 and 1000000000 (109), inclusive.
  • p1 will be between 1 and 1000000000 (109), inclusive.
  • p2 will be between 1 and 1000000000 (109), inclusive.

Examples

  1. 17

    7

    9

    Returns: 18

    18 = 7 * 0 + 9 * 2

  2. 17

    7

    13

    Returns: 20

    20 = 7 * 1 + 13 * 1

  3. 21

    7

    13

    Returns: 21

    21 = 7 * 3 + 13 * 0

  4. 37

    9

    17

    Returns: 43

    43 = 9 * 1 + 17 * 2

  5. 287341

    2345

    7253

    Returns: 287398

    287398 = 2345 * 104 + 7253 * 6

  6. 1000000000

    1

    1

    Returns: 1000000000

  7. 1000000000

    1000000000

    1

    Returns: 1000000000

  8. 1000000000

    1

    1000000000

    Returns: 1000000000

  9. 1000000000

    1000000000

    1000000000

    Returns: 1000000000

  10. 1000000000

    999999999

    999999999

    Returns: 1999999998

  11. 1

    1000000000

    999999999

    Returns: 999999999

  12. 3

    1000000000

    1000000000

    Returns: 1000000000

  13. 3

    999999997

    1000000000

    Returns: 999999997

  14. 999999913

    1

    992999913

    Returns: 999999913

  15. 999999913

    3

    992999913

    Returns: 999999915

  16. 999999913

    992999913

    1

    Returns: 999999913

  17. 999999913

    992999913

    3

    Returns: 999999915

  18. 536343

    288

    1

    Returns: 536343

  19. 26964

    111209082

    1291960

    Returns: 1291960

  20. 810

    1

    20533140

    Returns: 810

  21. 2920

    123773

    48048593

    Returns: 123773

  22. 2167

    302350

    63751

    Returns: 63751

  23. 951546

    104795

    6423

    Returns: 951947

  24. 53635841

    185343

    157

    Returns: 53635841

  25. 701317

    592510

    17742

    Returns: 709680

  26. 1

    1

    1754

    Returns: 1

  27. 208029086

    1197

    3

    Returns: 208029087

  28. 3827059

    3849166

    30735

    Returns: 3841875

  29. 386

    810183478

    42401940

    Returns: 42401940

  30. 2699

    4960290

    28

    Returns: 2716

  31. 1

    318551

    10

    Returns: 10

  32. 15206

    1072763

    552914

    Returns: 552914

  33. 875938

    1806952

    817

    Returns: 876641

  34. 414989

    3290136

    885

    Returns: 415065

  35. 313

    2013799

    38505

    Returns: 38505

  36. 444393

    79690

    1010

    Returns: 444400

  37. 566501015

    300551970

    2122343

    Returns: 566665581

  38. 6

    53

    3559949

    Returns: 53

  39. 53079295

    635

    252

    Returns: 53079295

  40. 8

    2

    14

    Returns: 8

  41. 164

    37

    1097119

    Returns: 185

  42. 2658007

    267491

    3047

    Returns: 2658096

  43. 31550

    4

    12659

    Returns: 31550

  44. 28220

    41272155

    470945368

    Returns: 41272155

  45. 842418187

    37

    438923

    Returns: 842418187

  46. 9

    137

    519185

    Returns: 137

  47. 900

    17159

    90

    Returns: 900

  48. 29

    15

    16

    Returns: 30

  49. 3913

    3581

    3

    Returns: 3914

  50. 3897537

    1625

    257

    Returns: 3897537

  51. 189290897

    146170

    176519597

    Returns: 189382557

  52. 17432

    1005

    5235

    Returns: 17505

  53. 8779251

    22617

    2570

    Returns: 8779255

  54. 495230

    14921

    27708

    Returns: 496627

  55. 223

    85

    3

    Returns: 223

  56. 93

    93

    3

    Returns: 93

  57. 1281

    155

    853

    Returns: 1318

  58. 64169488

    11055

    791792

    Returns: 64169570

  59. 136

    57

    4

    Returns: 136

  60. 120

    6

    92

    Returns: 120

  61. 17451

    57

    3

    Returns: 17451

  62. 2260

    1395

    1907

    Returns: 2790

  63. 1023

    45

    1

    Returns: 1023

  64. 131827436

    6

    8

    Returns: 131827436

  65. 31242

    2

    9605

    Returns: 31242

  66. 152

    14

    2

    Returns: 152

  67. 1

    1

    1

    Returns: 1

  68. 17262688

    3305956

    4

    Returns: 17262688

  69. 122

    11

    115

    Returns: 126

  70. 137699588

    1902247

    3

    Returns: 137699588

  71. 4819808

    69684

    3203483

    Returns: 4875899

  72. 35

    24

    27

    Returns: 48

  73. 1

    1

    1

    Returns: 1

  74. 6079

    2

    4591

    Returns: 6079

  75. 7

    5

    3

    Returns: 8

  76. 7486775

    4

    42

    Returns: 7486776

  77. 9

    1

    6

    Returns: 9

  78. 1928

    1131

    1765

    Returns: 2262

  79. 376402824

    243997730

    39372804

    Returns: 393728040

  80. 109681

    87002

    16877

    Returns: 118139

  81. 1359

    796

    1206

    Returns: 1592

  82. 1153

    866

    923

    Returns: 1732

  83. 2296

    2009

    709

    Returns: 2718

  84. 102608

    14107

    13578

    Returns: 108624

  85. 30

    5

    6

    Returns: 30

  86. 3154

    1615

    3127

    Returns: 3230

  87. 53917296

    1660012

    28216367

    Returns: 54776559

  88. 1

    1

    1

    Returns: 1

  89. 1

    2

    2

    Returns: 2

  90. 1

    2

    1

    Returns: 1

  91. 1

    1

    2

    Returns: 1

  92. 1000000000

    2

    3

    Returns: 1000000000

  93. 1000000000

    2

    4

    Returns: 1000000000

  94. 999999999

    2

    4

    Returns: 1000000000

  95. 999999999

    2

    3

    Returns: 999999999

  96. 999999999

    2

    2

    Returns: 1000000000

  97. 1000000000

    2

    2

    Returns: 1000000000

  98. 999999998

    2

    4

    Returns: 999999998

  99. 999999999

    4

    6

    Returns: 1000000000

  100. 287341

    2345

    7253

    Returns: 287398

  101. 999999991

    2

    2

    Returns: 999999992

  102. 21

    7

    13

    Returns: 21

  103. 666000000

    800000000

    7

    Returns: 666000006

  104. 999999937

    3

    5

    Returns: 999999937

  105. 1000000000

    3

    7

    Returns: 1000000000

  106. 999900007

    3

    17

    Returns: 999900007

  107. 1000000000

    1

    1

    Returns: 1000000000

  108. 1000000000

    3

    5

    Returns: 1000000000

  109. 1000000000

    1

    2

    Returns: 1000000000

  110. 1000000000

    3

    9

    Returns: 1000000002

  111. 287341

    332345

    237253

    Returns: 332345

  112. 999999999

    2

    4

    Returns: 1000000000

  113. 999999999

    2

    2

    Returns: 1000000000

  114. 999999999

    6

    7

    Returns: 999999999

  115. 1000000000

    3

    3

    Returns: 1000000002

  116. 1000000000

    4

    3

    Returns: 1000000000

  117. 990000012

    883212354

    999999943

    Returns: 999999943

  118. 100000000

    5

    3

    Returns: 100000000

  119. 1000000000

    6

    9

    Returns: 1000000002

  120. 100

    1

    101

    Returns: 100

  121. 1000000000

    7

    11

    Returns: 1000000000

  122. 999999997

    3

    5

    Returns: 999999997

  123. 1000000000

    10

    30

    Returns: 1000000000

  124. 1000000000

    7

    13

    Returns: 1000000000

  125. 1000000000

    11

    7

    Returns: 1000000000

  126. 1000000000

    399

    799

    Returns: 1000000000

  127. 999999997

    37

    29

    Returns: 999999997

  128. 100000007

    2

    3

    Returns: 100000007

  129. 999999937

    99991

    899981

    Returns: 1000009991

  130. 11

    5

    3

    Returns: 11

  131. 8

    3

    7

    Returns: 9

  132. 33

    2

    17

    Returns: 33

  133. 999999937

    2

    5

    Returns: 999999937

  134. 999999999

    4

    2

    Returns: 1000000000

  135. 999999995

    2

    3

    Returns: 999999995

  136. 1000000000

    7

    7

    Returns: 1000000001

  137. 1000000000

    999999999

    1000000000

    Returns: 1000000000

  138. 36

    7

    5

    Returns: 36

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: