Question
Given a non-negative amount N and a set of S coins of positive values Vi, return the number of ways to reach the required amount
Given a non-negative amount N and a set of S coins of positive values Vi, return the number of ways to reach the required amount using the coins. NB : You have an unlimited number of each coin at your disposal. For example, given N = 10, S = 2 and the set of values V1 = {1, 5} , you should return 3. Indeed, there are 3 ways to sum coins of values {1, 5} up to 10 : 1*10, 5*2 and 1*5 + 5*1.
Input Line 1 : A non-negative integer N for the target amount. Line 2 : A positive integer S for the number of possible values coins. Line 3 : S space-separated non-negative integer Vi for the value of the i-th coin.
Output An integer representing the number of ways to sum the coins up to N (0 if there is no way to reach the target amount).
Constraints 0 <= N <= 2000 0 < S <= 10 0 < Vi <= 500
Example:
Input 10 2 1 5
Output
3
Sample starting code:
#include
#include
#include
#include
using namespace std;
/**
* Auto-generated code below aims at helping you parse
* the standard input according to the problem statement.
**/
int main()
{
int N;
cin >> N; cin.ignore();
int S;
cin >> S; cin.ignore();
for (int i = 0; i < S; i++) {
int Vi;
cin >> Vi; cin.ignore();
}
cout << "answer" << endl;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started