357 - Let Me Count The Ways

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post 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).

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz

Post 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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post 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...

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz

Post 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
Last edited by Klechu on Tue May 04, 2004 12:15 pm, edited 1 time in total.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k »

Hi,

I have send your code and got AC.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post 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

[senu]
New poster
Posts: 6
Joined: Tue May 18, 2004 6:59 pm

357 again

Post 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.

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm

Post by 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
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

357 - Let Me Count The Ways

Post 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!!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

My program outputs:
There is only 1 way to produce 0 cents change.
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.

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post 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!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post 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.
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.

mb09
New poster
Posts: 2
Joined: Sun Jan 16, 2005 4:00 pm

357 exceed time limit

Post 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]

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: 357 exceed time limit

Post 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.

User avatar
dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

Hi!!! mb09

Post by dovier_antonio »

text removed...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:50 am, edited 2 times in total.

Post Reply

Return to “Volume 3 (300-399)”