Page 3 of 7
Posted: Sat Apr 24, 2004 12:15 pm
by 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).
Posted: Sat Apr 24, 2004 12:30 pm
by 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
Posted: Sat Apr 24, 2004 12:53 pm
by 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...
Posted: Sat Apr 24, 2004 1:14 pm
by 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
Posted: Mon Apr 26, 2004 8:25 pm
by prince56k
Hi,
I have send your code and got AC.
Posted: Mon Apr 26, 2004 8:32 pm
by 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
357 again
Posted: Tue May 18, 2004 7:06 pm
by [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.
Posted: Mon Jun 21, 2004 9:53 pm
by paulidirac
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
357 - Let Me Count The Ways
Posted: Sat Oct 09, 2004 10:19 pm
by 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!!
Posted: Sun Oct 10, 2004 4:29 pm
by ..
My program outputs:
There is only 1 way to produce 0 cents change.
Posted: Sun Oct 10, 2004 5:59 pm
by 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!
Posted: Sun Oct 10, 2004 6:23 pm
by ..
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.
357 exceed time limit
Posted: Sun Jan 16, 2005 4:03 pm
by 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]
Re: 357 exceed time limit
Posted: Fri Jan 21, 2005 7:16 pm
by 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.
Hi!!! mb09
Posted: Sun Mar 13, 2005 10:47 am
by dovier_antonio
text removed...