Connection Status:
Competition Arena > Shopping

Shopping

SRM 331 · 2006-12-21 · by slex

SRM 331 · 2006-12-21 · by slex · Greedy
Class Name: Shopping
Return Type: int
Method Name: minNumber
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

Christmas is coming soon and you still have so many things to buy. You are going to the store and don't expect to spend more than X dollars. You want to be able to pay any integer amount not exceeding X dollars, and you want to take as few coins as possible to achieve this.

You are given a int[] values, each element of which describes the dollar value of a kind of coin. You have an unlimited supply of each kind of coin. Return the minimal number of coins you need to take, or -1 if it is impossible to achieve your goal.

Constraints

  • X will be between 1 and 1000, inclusive.
  • values will contain between 1 and 10 elements, inclusive.
  • Each element of values will be between 1 and 1000, inclusive.
  • The elements in values will be distinct.
Examples
0)
5
{1}
Returns: 5
1)
1000
{1}
Returns: 1000
2)
1000
{1, 2}
Returns: 501
3)
5
{1, 2}
Returns: 3
4)
3
{1, 2}
Returns: 2
5)
20
{1, 2, 5, 10}
Returns: 5

Taking 5 coins with values {1,2,2,5,10} allows you to pay any integer amount between 1 and 20, inclusive.

20)
7
{2, 4, 1, 7}
Returns: 3

Here, taking {2,4,1} is enough.

34)
20
{2,4,6,8}
Returns: -1

These nominals allow you to pay only even amounts.

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

Coding Area

Language: C++17 · define a public class Shopping with a public method int minNumber(int X, vector<int> values) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous