357 - Let Me Count The Ways

[little joey]

Sohel: not completely true.
printf("%d",ll); can cause a segementation fault if ll is of type long long (but it will not always do that).

[Klechu]

here is my code. I have tried with many others data type but it don`t works with input like 29050, 30000 or 29950

[c]#include <stdio.h>
#include <stdlib.h>

long long t[30005];
int w[5]={1,5,10,25,50};
int i,j,n;
int main()
{
/*printf("%d",sizeof(t[0]));*/
t[0]=1;
for(j=0;j<5;j++)
for(i=w[j];i<30005;i++)
t += t[(i-(w[j]))];
while(scanf("%d",&n)==1)
{
(t[n]==1)?printf("%s%d%s\n","There is only 1 way to produce ",t[n]," cents change."):printf("%s%d%s%d%s\n","There are ",t[n]," ways to produce ",n," cents change.");
}
return 0;
}[/c]
Thanks for any kind of help
Klechu

[little joey]

That's exactly what I meant. Print long long using "%lld" instead of "%d" and you'll get rid of the runtime error. Don't know if it produces correct answers then...

[Klechu]

I do what you said and I have still had problems with errors (I havent send problem jet but I had a same problems as earlier at Dev-C++ (it`s base on gcc) I don`t know what to do with that :( O, I had forgot - first time I have got RE my program return code 11 to the system (I don`t know what does mean)

here is my code after changes
[c]Because code was accepted it has been deleted
[/c]

I`m a little mad ;)
Klechu

[prince56k]

Hi,

I have send your code and got AC.

[prince56k]

u said u got WA but i got RTE.
If i increased the size to 30001 then got TLE.
U should precaulate al possible outputs upto 30000.
then take input and print.
But u r calcuting everytime after taking input and that's the reason for TLE.

Hope it will help u

[[senu]]

i dont know what to do....

why it works:
[cpp]
#include <iostream>
#define max 30002
using namespace std;

int main(void)
{
int n;
long long t[max+1];
long long v[5]={1,5,10,25,50};
t[0]=1;
int i;
for (i=0;i<max;i++) t = 1;
for (i=5;i<max;i++) t+=t[i-5];
for (i=10;i<max;i++) t+=t[i-10];
for (i=25;i<max;i++) t+=t[i-25];
for (i=50;i<max;i++) t+=t[i-50];

while (cin>>n)
if (t[n]==1){
cout << "There is only 1 way to produce " << n << " cents change." << endl;}
else{
cout << "There are " << t[n] << " ways to produce " << n << " cents change. " << endl;}

return 0;
}
[/cpp]

but this not ...
[cpp]#include <iostream>
#define max 30002
using namespace std;

int main(void)
{
int n;
long long t[max+1];
long long v[5]={1,5,10,25,50};
t[0]=1;
for (int i=0; i<=4; i++)
{
for(int j=v; j<max; j++)
{
t[j]+=t[j-v];
}
}


while (cin>>n)
if (t[n]==1){
cout << "There is only 1 way to produce " << n << " cents change." << endl;}
else{
cout << "There are " << t[n] << " ways to produce " << n << " cents change. " << endl;}

return 0;
}[/cpp]

???

diff start from n=308 and i dont know why
i dont wanna put not my code so plz help me.

[paulidirac]

that's cos in the first program, u've got this line

Code: Select all

for (i=0;i<max;i++) t[i] = 1; 

which sets all elements of t initially..
on the other hand, in the 2nd code, u r using a for loop and u don't know the value of the array elements.. they're all garbage cos ur variables r not declared global.. so to solve ur problem, just declare the array t as global...
enjoy

[txandi]

I can't understand. I get AC in 147 but WA in 357 and both problems are almost the same.

I need some help. Can anybody check my code?

[cpp]#include <iostream>
#define MAX 31000

using namespace std;

int coin[5]={50,25,10,5,1};

int main()
{
long long int total[MAX+1];

total[0]=1;
for(int i=0;i<5;i++)
{
int a=coin;
for(int j=a;j<=MAX;j++)
total[j]+=total[j-a];
}
total[0]=0;

int n;
while (cin >> n)
{
if(total[n]!=1) cout << "There are "<< total[n]<<" ways to produce " << n <<" cents change." << endl;
else cout << "There is only 1 way to produce "<< n <<" cents change." << endl;
}
return 0;
}[/cpp]
Thanks a lot!!

[..]

My program outputs:
There is only 1 way to produce 0 cents change.

[txandi]

Now my program gets AC, but I think OJ should avoid confusing inputs, like 0 in this case... I've wasted a lot of time looking for bugs in my code.

Anyway, thanks a lot!

[..]

Well, I think it is natural to have 1 way for constructing 0.
Since in the set theory, an ampty set is also a set.

[mb09]

here is my code...
i run very fast in my own pc.....
but exceed time limit in online judge...
can anyone tell me why?

Code: Select all

#include<iostream>
using namespace std;

int main()
{
	long long int count=0;
	int input,backup,temp,temp2;

	while(cin>>input)
	{
		backup=input;
		input-=input%5;
		for (int i=0;i<=input*0.02;i++)
			for (int j=0;j<=(input-(i*50))*0.04;j++)
			{
				temp=(input-(i*50)-(j*25))*0.2+1;
				temp2=temp>>1;
				if (temp%2==0)
					count+=temp2*(temp2+1);
				else
					count+=temp2*(temp2+2)+1;
			}
		if (count==1)
			cout<<"There is only 1 way to produce "<<backup<<" cents change.\n";
		else cout <<"There are "<<count<<" ways to produce "<<backup<<" cents change.\n";
		count=0;
	}
	return 0;
}

[/code]

[nnahas]

I think your code is too slow. a O(1) solution (i.e closed form solution) is possible. But even if you don't find it, try to build a table in O(N) time, to get the number of ways for each integer between 1 and 30000 and then for each input just look up its value, instead of running the algo for each input. A solution along these lines has been posted on this message board, try to find it by typing 357 in search input box.

[dovier_antonio]

text removed...