Suppose a coin machine sells subway tickets (such as at the DC Metro), where eve

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)

Note: Do not use vectors

Explanation / Answer

//The following code provides the number of ways of paying for a ticket costing upto 1000 cents

#include<iostream>

using namespace std;

int main()

{

int amount;

unsigned long long int arr[1001]={0};

arr[0]=0;

arr[5]=0;

arr[10]=1;

arr[15]=0;

arr[20]=1;

arr[25]=1;

for(int i=30;i<=1000;i=i+5)

{

arr[i]=arr[i-10]+arr[i-25];

}

cout<<"Enter the amount : ";

cin>>amount;

if(amount%10!=0)

cout<<"Incorrect Amount!!! ";

else

cout<<"Number of ways for paying "<<amount<<" cents : "<<arr[amount]<<endl;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.