Suppose a coin machine sells subway tickets (such as at the DC Metro), where eve
ID: 3548717 • Letter: S
Question
Suppose a coin machine sells subway tickets (such as at the DC Metro), where every ticket is a multiple of 10 cents. The machine accepts only dimes and quarters (no nickels or pennies).
For example, 50 cents can be done exactly two different ways:
two quarters in sequence, or 5 dimes in sequence.
On the other hand, 60 cents can be done four different ways:
two quarters followed by a dime; a dime followed by two quarters;
quarter, then a dime, then a quarter; or six dimes in sequence.
Hint: insert one coin at a time.
For 60 cents -- insert a dime, and there are two ways to insert 50 cents;
or insert a quarter, and there are two ways to insert 35 cents.
Write this code by creating a loop (filling an array like a dynamic programming problem)
Explanation / Answer
#include<iostream>
#include<conio.h>
using namespace std;
int C[] = {10, 25};
int check(int n, int k)
{
vector<vector<int> > table(n+1, vector<int>(k+1, 1));
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
if (i < 0 || j < 0) // Impossible
{
table[i][j] = 0;
}
else if (i == 0 || j == 0) // Critical Condition
{
table[i][j] = 1;
}
else
{
table[i][j] = table[i][j-1] +
(i < C[j] ? 0 : table[i-C[j]][j]);
}
}
}
return table[n][k];
}
int main()
{
cout << "Answer: "<< check(60, 1) ;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.