Connection Status:
Competition Arena > ChangePurse

ChangePurse

SRM 195 · 2004-05-18 · by schveiguy

SRM 195 · 2004-05-18 · by schveiguy · Advanced Math
Class Name: ChangePurse
Return Type: int[]
Method Name: optimalCoins
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. If multiple ways exist to give Johnny change, return the one with the most coins of the highest denomination. If multiple ways exist which have the most coins of the highest denomination, return the one with the most coins of the second-highest denomination, and so on. 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, and even though it does not produce the fewest coins, the first way is preferable because it contains a high-valued 25 cent piece.

You will be given a int[] coinTypes, which will be a list containing the value of each type of coin in the given 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 1000000, 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 1000000000, inclusive.
Examples
0)
{1,25,10}
49
Returns: { 24,  1,  0 }

The example from the problem statement.

1)
{1,7}
49
Returns: { 49,  0 }

Note that {7,6} is an invalid return because even though it equals 49 cents, and it allows all values between 1 and 49, it would allow multiple ways to make 7 cents. This is the thing that Johnny fears the most.

2)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
390700799
Returns: { 4,  0,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  19535039 }
3)
{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288}
1048575
Returns: { 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1 }
4)
{11,5,10,1}
109
Returns: { 9,  0,  0,  10 }

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 ChangePurse with a public method vector<int> optimalCoins(vector<int> coinTypes, int value) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous