Connection Status:
Competition Arena > AmountApproximation

AmountApproximation

SRM 274 · 2005-11-23 · by Andrew_Lazarev

SRM 274 · 2005-11-23 · by Andrew_Lazarev · Simple Math
Class Name: AmountApproximation
Return Type: int
Method Name: approximate
Arg Types: (int, int, int)
Problem Statement

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.

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
0)
17
7
9
Returns: 18

18 = 7 * 0 + 9 * 2

1)
17
7
13
Returns: 20

20 = 7 * 1 + 13 * 1

2)
21
7
13
Returns: 21

21 = 7 * 3 + 13 * 0

3)
37
9
17
Returns: 43

43 = 9 * 1 + 17 * 2

4)
287341
2345
7253
Returns: 287398

287398 = 2345 * 104 + 7253 * 6

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

Coding Area

Language: C++17 · define a public class AmountApproximation with a public method int approximate(int D, int p1, int p2) · 138 test cases · 2 s / 256 MB per case

Submitting as anonymous