NewCoins
Member SRM 458 · 2009-12-03 · by rng_58
Member SRM 458 · 2009-12-03 · by rng_58 · Dynamic Programming
Problem Statement
Problem Statement
As a finance minister, Bob decided to make new denominations of coins. If the values of the coins are x1, x2, x3, ... in ascending order then x1 must be 1 and xb must be an integer multiple of xa for all b > a.
He has a list of products sold in his country. The price of the i-th product is price[i]. He wants to minimize the number of coins required to buy each product exactly once. Each product must be purchased separately using coins that total to exactly the value of the product. Using multiple coins of the same denomination is allowed. See example 0 for further clarification.
Return the minimal number of coins required to buy each product exactly once.
He has a list of products sold in his country. The price of the i-th product is price[i]. He wants to minimize the number of coins required to buy each product exactly once. Each product must be purchased separately using coins that total to exactly the value of the product. Using multiple coins of the same denomination is allowed. See example 0 for further clarification.
Return the minimal number of coins required to buy each product exactly once.
Constraints
- price will contain between 1 and 50 elements, inclusive.
- Each element in price will be between 1 and 100,000, inclusive.
Examples
0)
{25, 102}
Returns: 4
Bob can use {1, 25, 100} as the new set of coins. Then, a single coin of value 25 can be used to buy the first product. To buy the second product, one coin of value 100 and two coins of value 1 is sufficient. So, in total, 4 coins can be used to buy all products using the new set of coins.
1)
{58}
Returns: 1
One possible set of coins is {1, 58}.
2)
{1, 4, 5, 9, 16}
Returns: 7
One possible set of coins is {1, 2, 4, 8, 16}.
3)
{1, 1, 1, 1, 1}
Returns: 5
Different products may have the same price.
4)
{28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498}
Returns: 62
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NewCoins with a public method int minCoins(vector<int> price) · 107 test cases · 2 s / 256 MB per case