674 - Coin Change

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

Moderator: Board moderators

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Re: About CLRS

Post by 58050zz » Sat Apr 02, 2005 11:52 am

Raj Ariyan wrote: Try to read this book when u will free. It will help you much. Greedy most probably in chapter 16.
Greedy is in ch16
do i use Greedy to slove this?


to sohel:
my code is not AC is TLE^^

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Apr 02, 2005 4:49 pm

58050zz wrote: to sohel:
my code is not AC is TLE^^
I was not refering to your code.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Post by 58050zz » Sun Apr 03, 2005 2:54 am

sohel wrote:Hi,
From your code it looks like you are using brute force. And that should obviously get TLE.

Implementation of DP:
1) declare an int array of size 7500
2) initialize all the elements with 0
3) set Array[0] = 1; --- because there is only one way of making zero ie
'by not choosing any coin'.

4) for every coin run a loop from j = 1 to 7500
set Array[ coinvalue + j] += Array[j];
5) END

Hope it helps.
:wink:
i use ur algorithm and slove ok for 674
but WA for 147
can u tell me why?

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Post by 58050zz » Sun Apr 03, 2005 2:56 am

do ur algorithm here

==output here
while(cin>>target)
{
cout.width(6);
cout.precision(2);
cout<<target;
if(target==0)return 0;
int tar=(int)(target*100);

cout<<setw(17)<<setiosflags(ios::right)
<<Array[tar]<<endl;
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Apr 03, 2005 8:36 am

58050zz wrote:
while(cin>>target)
{
cout.width(6);
cout.precision(2);
cout<<target;
if(target==0)return 0;
int tar=(int)(target*100);

cout<<setw(17)<<setiosflags(ios::right)
<<Array[tar]<<endl;
}
I think the error could be in handling the conversion of floating point number to integer.
There are other posts related to this problem.
.. 5.00 * 100 is not equal to 500, instead it is 499.

try to convert int tar = (int)(target*100) to
int tar = (int)(target*100 + 0.001 ).

Hope it helps.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am

Post by 58050zz » Sun Apr 03, 2005 4:35 pm

thank you ,
for your help
i get AC
:D

devilshit
New poster
Posts: 1
Joined: Wed Jul 20, 2005 7:29 am

674 output limit exced

Post by devilshit » Sat Aug 20, 2005 9:43 am

I don't know why I get the problem. Please help. :-?

Code: Select all

while(scanf("%d", &n) != 0)
        printf("%d\n", dp[n]);
dp[n] = storing the number of way(int) when there is n-cent

This code works fine on my machine(winxp, visual c++ 6.0)

zhuo
New poster
Posts: 2
Joined: Sun Feb 05, 2006 5:47 pm
Location: taiwan

674: Coin Change WA

Post by zhuo » Sun Feb 05, 2006 5:56 pm

I've tried a lot of test data, but I still got WA.
Why?? ~ help, please

Code: Select all

#include<stdio.h>/* 674 357 147*/

int main(){
	int a[30001][4],t;
	int i,tol,n;

	for(i=0;i<5;i++){
		a[i][0]=0; 
		a[i][1]=0;
		a[i][2]=0;
		a[i][3]=0;
	}
	tol=4;
	
	while( scanf("%d",&n)!=EOF ){
		
		if(n>tol){
			for( ; tol<=n ;tol++){
				if( tol>=50)
					a[tol][0]=a[tol-50][0]+a[tol-50][1]+a[tol-50][2]+a[tol-50][3]+1;
				else
					a[tol][0]=0;

				if( tol>=25)
					a[tol][1]=a[tol-25][1]+a[tol-25][2]+a[tol-25][3]+1;
				else
					a[tol][1]=0;

				if( tol>=10)
					a[tol][2]=a[tol-10][2]+a[tol-10][3]+1;
				else
					a[tol][2]=0;

				if( tol>=5)
					a[tol][3]=a[tol-5][3]+1;
				else
					a[tol][3]=0;
			}
		}
		
		t=a[n][0]+a[n][1]+a[n][2]+a[n][3]+1;
		printf("%d\n",t);
		/*if(t!=1)
			printf("There are %d ways to produce %d cents change. \n",t,n);
		else	
			printf("There are 1 way to produce %d cents change. \n",n);*/
		
	}
	return 0;
}

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Feb 05, 2006 9:20 pm

Input

Code: Select all

5
6
Output

Code: Select all

2
2

zhuo
New poster
Posts: 2
Joined: Sun Feb 05, 2006 5:47 pm
Location: taiwan

AC

Post by zhuo » Mon Feb 06, 2006 7:06 am

I got accepted . I done a stupid mistake.
Thanks a lot. :D

Rocklets
New poster
Posts: 2
Joined: Wed Nov 12, 2008 10:07 pm

Re: 674 - Coin Change why TLE?

Post by Rocklets » Thu Nov 13, 2008 6:33 am

why this code have TLE?

Code: Select all

edited afer AC

tanvir_cse
New poster
Posts: 9
Joined: Wed Jul 09, 2008 10:12 pm

674 -- TLE : need Good Algorithm

Post by tanvir_cse » Sat Dec 06, 2008 2:59 pm

Hi,Iam suffering a lot, and need an algorithm badly. Anybody Help me

Code: Select all

#include<stdio.h>
#include<iostream.h>
#include<string.h>

int cent_1(int mon);
int cent_5(int mon);
int cent_10(int mon);
int cent_25(int mon);
int cent_50(int mon);

int count=0;
 
int main(void)
{
	int cent, sum;
	while(scanf("%d",&cent)!=EOF)
	{
		count=0;
		if(cent>=1 && cent<=4)
		{
			printf("%d\n",cent_1(cent));
		}
		if(cent>=5 && cent<=9)
		{
			sum=0;
			if(cent==5)
				sum=1;
			sum+=cent_1(cent);
			sum+=cent_5(cent);
			printf("%d\n",sum);
		}
		if(cent>=10 && cent<=24)
		{
			sum=0;
			if(cent==10)
				sum+=1;

			sum+=cent_1(cent);
			sum+=cent_5(cent);
			sum+=cent_10(cent);

			printf("%d\n",sum);
		}
		if(cent>=25 && cent<=49)
		{
			sum=0;
			if(cent==25)
				sum+=1;

			sum+=cent_1(cent);
			sum+=cent_5(cent);
			sum+=cent_10(cent);			
			sum+=cent_25(cent);

			printf("%d\n",sum);
		}
		if(cent>=50)
		{
			sum=0;
			if(cent==50)
				sum+=1;

			sum+=cent_1(cent);
			sum+=cent_5(cent);
			sum+=cent_10(cent);			
			sum+=cent_25(cent);
			sum+=cent_50(cent);

			printf("%d\n",sum);
		}
	}
}



int cent_1( int mon)
{

	if(mon==0)
		return 0;

	return 1;

}


int cent_5( int mon)
{
	int i,m,t=0,temp;

	if(mon==0)
		return 0;

	m=mon/5;
	for(i=m; i>0; i--)
	{
		temp=mon-5*i;
		t=t+cent_1(temp);
	}

	return t;

}



int cent_10( int mon)
{
	int i,m,t=0,temp;
	if(mon==0)
		return 0;

	m=mon/10;
	for(i=m; i>0; i--)
	{
		temp=mon-10*i;
		t=t+cent_1(temp);
	}

	for(i=m; i>0; i--)
	{
		temp=mon-10*i;
		t=t+cent_5(temp);
	}

	return t;
}


int cent_25( int mon)
{
	int i,m,t=0,temp;
	if(mon==0)
		return 0;

	m=mon/25;
	for(i=m; i>0; i--)
	{
		temp=mon-25*i;
		t=t+cent_1(temp);
	}

	for(i=m; i>0; i--)
	{
		temp=mon-25*i;
		t=t+cent_5(temp);
	}

	for(i=m; i>0; i--)
	{
		temp=mon-25*i;
		t=t+cent_10(temp);
	}

	return t;
}

int cent_50( int mon)
{
	int i,m,t=0,temp;
	if(mon==0)
		return 0;

	m=mon/50;
	for(i=m; i>0; i--)
	{
		temp=mon-50*i;
		t=t+cent_1(temp);
	}

	for(i=m; i>0; i--)
	{
		temp=mon-50*i;
		t=t+cent_5(temp);
	}

	for(i=m; i>0; i--)
	{
		temp=mon-50*i;
		t=t+cent_10(temp);
	}

	for(i=m; i>0; i--)
	{
		temp=mon-50*i;
		t=t+cent_25(temp);
	}

	return t;
}


mimi
New poster
Posts: 5
Joined: Fri Dec 19, 2008 6:39 pm

TLE

Post by mimi » Fri Dec 19, 2008 6:42 pm

I got tle. Will anybody see my code and tell me where i am wrong. Thanks in advance.
Here is my code:

import java.io.*;

public class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
int n = Integer.parseInt(vhod.readLine());
System.out.println(coinchange(n));
}
}
public static int coinchange(int n)
{
int tab[]=new int[7490];
int coin[] = new int[5];
coin[0]=1;
coin[1]=5;
coin[2]=10;
coin[3]=25;
coin[4]=50;
for(int i = 0; i < 7490; i++)
{
tab = 0;
tab[0] = 1;
}
for(int i = 0; i < 5; i++)
{
int c = coin;
for(int j = c; j < 7490; j++)
{
tab[j] += tab[j-c];
}
}
return tab[n];
}
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: TLE

Post by mf » Fri Dec 19, 2008 7:23 pm

Your code recomputes a big array (int tab[]=new int[7490]) for every case.
Of course this is making your program many thousands times slower than it could be if you computed this array only once, what'd you expect? Compiler's not smart enough to move the computation of that array out of the main loop for you.

mimi
New poster
Posts: 5
Joined: Fri Dec 19, 2008 6:39 pm

TLE

Post by mimi » Fri Dec 19, 2008 9:53 pm

Can you please tell me how to change my program to compute this array only once :oops: Thanks

Post Reply

Return to “Volume 6 (600-699)”