357 - Let Me Count The Ways

[chinmoy kanti dhar]

give some input output plz?

30000= 543427145501
20000= 107683177001
0=1
is these output are right?

[Jan]

Your cases are correct. You can post your code.

[chinmoy kanti dhar]

but i am getting wrong answer.here is the code-

[code]
cut after AC
[/code]

[helloneo]

You don't even pass the sample test case..
See the output description carefully..

[tuman]

Handle "are" "is" carefully.
You code is ok. it will get accepted.
Ur logic is cool. just change it and dont need to change ur logic at all.....
dont do coding while sleeping :wink

somebody could have helped u b4 by telling that silly mistake rather than making fun out of sample output. This kindah fault is really annoying....

[chinmoy kanti dhar]

thanks.now i have accepted it.

[rhsumon]

Anyone say about this.........
Why Time L E Plz ...........

Code: Select all

#include <stdio.h>
#define MAXTOTAL 30000
long long  nway[MAXTOTAL+5];
int coin[5] = { 50,25,10,5,1 };

void main()
{
	int i,j,n,v,c;
	while(scanf("%d",&n) == 1){
		for(i=0; i<=n; i++) nway[i] = 0;
		v = 5;
		nway[0] = 1;
		for (i=0; i<v; i++){
			c = coin[i];
			for (j=c; j<=n; j++)
				nway[j] += nway[j-c];
		}
		printf("There are %lld ways to produce %d cents change.\n",nway[n],n);
	}
}

[Jan]

Just precalculate all. Then take input show the calculated result. [You are taking input and then calculating.]

[ishtiaq ahmed]

This program is compilation error. can anyone help me? Here is my code

Code: Select all

The code is removed after AC. Thanks for replying.

[Bappi_cuet]

replace void main() to int main(). Hope its help.

[WingletE]

long long int total[MAX+1];

total[0]=1;
for(int i=0;i<5;i++)
{
...
}
...

Why isn't it necessary to set all the elements in 'total' to zero before using it?

[andmej]

long long int total[MAX+1];

total[0]=1;
for(int i=0;i<5;i++)
{
...
}
...

Why isn't it necessary to set all the elements in 'total' to zero before using it?

Because all values in an array are defaulted to 0. For instance, if you run this code

Code: Select all

#include <iostream>
using namespace std;
int a[10];
int main(){
	for (int i=0; i<10; ++i) cout << a[i] << " ";
	cout << endl;
	return 0;
}

you will get

Code: Select all

0 0 0 0 0 0 0 0 0 0 

as an output.

Now, I need a little help in understanding this dynamic programming solution. I can't see how it works.

I know dynamic programming is simply used to avoid recalculating repeated operations, so there must exist a recursive function that gives me the solution of this problem.

Let f(n) be a function that returns the number of ways you can make n cents (i.e, the solution for n). How can I define f(n) in terms of f(n-i)? i.e, how can I define f(n) in a recursive way?

Thanks!

[Obaida]

I don't know why it doesn't work for 30000. someone please help me.

Code: Select all

Accepted Now

[andmej]

You have two bugs:

1. You should change the definition of the array ways from long to long long.
2. You are using <=MAX in your loops, but in the worst case MAX can be 30001 and you would have problems because the array ways has only 30001 positions, that is, it has position from index 0 to index 30000; index 30001 would be using memory that doesn't belong to the array.

You can fix both problems by changing:

Code: Select all

#define MAX 30001
long ways[MAX];

to

Code: Select all

#define MAX 30000
long long ways[MAX+1];

You also need to manage the case of only one way to get accepted.

Good luck!

[Obaida]

Code: Select all

Thanks Andmej I got Accepted

Sometimes I did such kind of mistake I didn't checked my output with the sample case carefully.
Thank you again ! Hope to be careful in future.