357  Let Me Count The Ways
Moderator: Board moderators

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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
[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

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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 DevC++ (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
here is my code after changes
[c]Because code was accepted it has been deleted
[/c]
I`m a little mad ;)
Klechu
Last edited by Klechu on Tue May 04, 2004 12:15 pm, edited 1 time in total.
357 again
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[i5];
for (i=10;i<max;i++) t+=t[i10];
for (i=25;i<max;i++) t+=t[i25];
for (i=50;i<max;i++) t+=t[i50];
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[jv];
}
}
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.
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[i5];
for (i=10;i<max;i++) t+=t[i10];
for (i=25;i<max;i++) t+=t[i25];
for (i=50;i<max;i++) t+=t[i50];
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[jv];
}
}
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.

 New poster
 Posts: 5
 Joined: Mon Jun 07, 2004 9:00 pm
that's cos in the first program, u've got this line
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
Code: Select all
for (i=0;i<max;i++) t[i] = 1;
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
357  Let Me Count The Ways
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[ja];
}
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!!
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[ja];
}
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!!
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.
Since in the set theory, an ampty set is also a set.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
357 exceed time limit
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]
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;
}
Re: 357 exceed time limit
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
 New poster
 Posts: 47
 Joined: Fri Feb 18, 2005 5:00 am
 Location: Havana, Cuba
Hi!!! mb09
text removed...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:50 am, edited 2 times in total.