Connection Status:
Competition Arena > ChangeOptimizer

ChangeOptimizer

SRM 195 · 2004-05-18 · by schveiguy

SRM 195 · 2004-05-18 · by schveiguy · Advanced Math
Class Name: ChangeOptimizer
Return Type: int[]
Method Name: fewestCoins
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Johnny Indecision has a change purse with some change in it. However, he is deathly afraid of having to figure out what might happen if he has to spend some of it. This fear arises because there may be more than one way to give out a certain amount of change. For example, if he has 1 dime (worth 10 cents) and 2 nickels (worth 5 cents apiece), there are two ways to make 10 cents. He also does not want to incur any more change, so he wants to be sure that he has exact change for any amount up to the amount of money he has.

So he would like to exchange his current change with some more predictable coins at the bank. As the bank clerk, you must solve Johnny's dilemma by giving him enough change to allow him to be able to spend any amount of money up to the amount he currently has, but the coins you give him must provide exactly one way to make each of those amounts. In addition, he would like to have as few coins as possible, even if it means having more smaller denomination coins. For example, if Johnny brings 49 cents to the bank, and the only coins available are 1, 10, and 25 cent pieces, there are three valid options:

  1. one 25-cent piece and 24 1-cent pieces
  2. four 10-cent pieces and nine 1-cent pieces
  3. 49 1-cent pieces
Each of these combinations results in only one way to make 1 to 49 cents, but the second way is preferable because it has the least number of coins of the three options. If multiple ways exist which have the fewest coins possible, return the way which has the most coins of the highest denomination. If multiple ways have an equal number of coins with the highest denomination, then return the way with the most coins of the second highest denomination, and so on. For example, with a monetary system that includes 1, 3, 6, and 2-cent pieces, and a balance of 11 cents, there are two answers with four coins:
  1. two 1-cent pieces, a one 3-cent piece, and a 6-cent piece
  2. one 1-cent piece, two 2-cent pieces, and a 6-cent piece
The first way is preferable because of its higher valued 3-cent piece.

You will be given a int[] coinTypes, which will be a list containing the value of each type of coin in the monetary system (which will always include a coin valued at 1). You will also be given an int value specifying the amount of money Johnny has. The return value should be a int[] indicating how many coins of each type you should give Johnny back. Element i of the return value should be how many coins valued at coinTypes[i] should be given to Johnny.

Constraints

  • coinTypes has between 1 and 50 elements, inclusive.
  • Each element of coinTypes is between 1 and 100,000,000, inclusive.
  • There will be no repeated values in coinTypes.
  • There will be exactly one element in coinTypes equal to 1.
  • value is between 1 and 1,000,000,000, inclusive.
Examples
0)
{1,10,25}
49
Returns: { 9,  4,  0 }

From the problem statement

1)
{1,3,6,2}
11
Returns: { 2,  1,  1,  0 }

From the problem statement

2)
{1,2,3,4,5,6,7,8,9,10}
1234567
Returns: { 1,  1,  0,  1,  0,  0,  0,  154320,  0,  0 }
3)
{91001,3567,222123,4456,1,732234,123793,982312,14781}
65864135
Returns: { 0,  0,  0,  0,  14780,  0,  0,  0,  4455 }
4)
{1,10,100,1000,10000}
1000000
Returns: { 1000000,  0,  0,  0,  0 }

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

Coding Area

Language: C++17 · define a public class ChangeOptimizer with a public method vector<int> fewestCoins(vector<int> coinTypes, int value) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous