Need a C code for this problem John, Stephen, and Nick like to eat dinner togeth

Question

Need a C code for this problem

John, Stephen, and Nick like to eat dinner together sometimes, but they've found one aspect of these dinners to be boring - paying the check! Splitting it evenly is simple: just divide by three. The most interesting part of this method is when the check doesn't split evenly and someone may have to pay a penny or two more than the others. Of course, this is still hardly interesting. John has devised a game to make paying the check more fun! John will only pay with $10 bills, Nick will only pay with $5 bills, and Stephen will only pay with $2 bills (assume everyone has an ample supply of their respective bill type to be capable of paying more than the entire bill). They will each keep laying down bills in any order in a pile until that pile adds up exactly to the total on the check (luckily, they only go to restaurants that are priced so this actually works!). They are all smart, so they never make mistakes that force the sum over the total. Now Nick is worried: how fast will this game get boring? Or, more specifically, given an amount representing the check total, how many different piles can be made with this method to sum up to exactly this amount? A pile is defined as different from another if there is either a different number of one or more of the bills or if the bills occur in a different order. Bills of the same denomination are indistinguishable, though. So, for example, all of the following piles are different from each other for various reasons: 2+2+5, 2+5+2, 5+2+2, 5+5+5, 2+5, 2+5+10, 10+10.

The Problem: Given the amount of the check total, how many different ways are there for John, Stephen, and Nick to make piles that sum up to exactly that amount?

The Input: The first line of input will be a positive number, c, the number of checks for which they want an answer. Following this will be c lines each describing one check. Each of these lines will contain an integer, t (1 t 50), representing the total amount of this check.

The Output: For each check, output a single integer representing the number of different ways to sum up to exactly the check total using the method described above.

Sample Input:

4

1

2

7

50

Sample Output:

0

1

2

52524

Explanation / Answer

#include<stdio.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
int inc[50],w[50],sum,n;
int tot=0;
int promising(int i,int wt,int total)
{

return(((wt+total)>=sum)&&((wt==sum)||(wt+w[i+1]<=sum)));
}

int main()
{
int i,j,n,temp,total=0,k;

printf(" Enter the number (first-1) line number: ");
scanf("%d",&n);
printf(" Enter those %d values: ",n);
for(i=0;i<n;i++)
{
scanf("%d",&w[i]);
total+=w[i];
}

printf(" Enter the Sum: ");
scanf("%d",&sum);
for(i=0;i<=n;i++)
for(j=0;j<n-1;j++)
if(w[j]>w[j+1])
{
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
}

if((total<sum)){
printf(" BILL payment is not possible because Total is = %d ",total);
exit(0);
}
else
{
for(i=0;i<n;i++)
inc[i]=0;
printf(" The Possible payments are: ");
sumset(-1,0,total);

}
printf("Total count is = %d ",tot*2);

return 0;
}
void sumset(int i,int wt,int total)
{
int j;

if(promising(i,wt,total))
{

if(wt==sum)
{
tot++;
printf(" { ");
for(j=0;j<=i;j++)
if(inc[j])
printf("%d ",w[j]);

printf("} ");

printf(" { ");
for(j=i;j>=0;j--)
if(inc[j])
printf("%d ",w[j]);
printf("} ");

}
else
{
inc[i+1]=TRUE;
sumset(i+1,wt+w[i+1],total-w[i+1]);
inc[i+1]=FALSE;
sumset(i+1,wt,total-w[i+1]);
}

}

}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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