ChangeOMatic
SRM 420 · 2008-10-01 · by misof
Problem Statement
The Change-O-Matic is a deterministic machine with a single goal: to provide change. That is, you throw in a banknote or a coin, and the machine throws out a bunch of smaller coins with the same total value.
More precisely, the Change-O-Matic operates as follows:
The machine contains several large stacks of coins. The values of these coins are given as a
The customer may throw in any coin or banknote with value greater than 1. The machine will output a set of at least two coins with the same total value. If there are multiple ways to satisfy this requirement, the machine prefers the one where the total number of output coins is minimized. If there are still multiple ways, the machine prefers the one that is lexicographically maximal (see Notes for a precise definition).
You have a single banknote, and its value is given as a
Notes
- Let A=(a1,...,aN) and B=(b1,...,bN) be two different but equally large sets of coins, with a1 >= a2 >= ... >= aN and b1 >= b2 >= ... >= bN. Let x be the smallest index such that ax != bx. If ax > bx, we say that the set A is lexicographically larger than the set B.
- Given a collection of different but equally large sets of coins, the lexicographically maximal set is the one that is lexicographically larger than each of the other sets. (Note that there is always exactly one such set.)
Constraints
- outputValues will contain between 1 and 50 elements, inclusive.
- outputValues will be sorted in strictly ascending order. That is, for each i, outputValues[i] < outputValues[i+1].
- Each element of outputValues will be between 1 and 1,000, inclusive.
- Element 0 of outputValues will be equal to 1.
- inputValue will be between 2 and 10^15, inclusive.
{1,5,10}
21
Returns: 7
The process of changing your money may look as follows: You insert: You get: You then have: 21 10+10+1 10+10+1 10 5+5 10+5+5+1 5 1+1+1+1+1 10+5+1+1+1+1+1+1 10 5+5 5+5+5+1+1+1+1+1+1 5 1+1+1+1+1 5+5+(eleven times 1) 5 1+1+1+1+1 5+(sixteen times 1) 5 1+1+1+1+1 twenty-one coins worth 1 each
{1,33,90,91,92,93,94,95,96,97,98}
99
Returns: 12
In each step, the machine minimizes the number of coins it throws out, not the number of steps you need to accomplish your task. In the first step it will output a coin worth 98 and a coin worth 1.
{1,30,60}
50
Returns: 2
The value of the banknote may be less than the values of some coin types.
{1,30,60,90}
60
Returns: 3
The value of the banknote may even be equal to the value of some coin type. Note that for any input the machine must always output at least two coins. Therefore if you throw in the banknote worth 60, you will get two coins worth 30 each.
{1,8,9,11,12,100}
120
Returns: 37
In the first step the machine would output 100+12+8. (The combination 100+11+9 has the same number of coins, but 100+12+8 is lexicographically larger.)
Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChangeOMatic with a public method long long howManyRounds(vector<int> outputValues, long long inputValue) · 133 test cases · 2 s / 256 MB per case