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

Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia

Post by Alexei Rybalkin » Tue Dec 02, 2003 5:56 pm

Thank you and good luck! :D
Last edited by Alexei Rybalkin on Thu May 06, 2004 1:13 pm, edited 1 time in total.

Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia

Post by Alexei Rybalkin » Tue Dec 02, 2003 6:42 pm

But I don't know what's wrong with my algorithm... :(

Can you help me?

Thanks

[cpp]
The code is wrong
[/cpp]
Last edited by Alexei Rybalkin on Thu May 06, 2004 1:16 pm, edited 1 time in total.

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Fri Dec 05, 2003 11:45 am

The reason is that it should be done this way:

Having computed the number of ways to do it with k coins, compute the number of ways of doing it with k+1 coins. That means, you must add only 1 coin at a time. PS: From this point of view, it's hard to interpret what your code does. :D

Also, you should change "long m[7489]" to "long m[7490]".

Good luck! :)

Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia

Post by Alexei Rybalkin » Fri Dec 05, 2003 1:36 pm

My code is wrong :cry:

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

674 TLE

Post by Zhao Le » Sat Dec 20, 2003 11:19 am

I know my algorithm is bad also wanna know how to use DP in my algorithm.
Thanks in advance.
[cpp]#include <iostream.h>

void C5(int n,int& count)
{
if(n >= 5)
{
n /= 5;
count += n;
}
}

void C10(int n,int& count)
{
if(n >= 10)
{
while(n >= 10)
{
n -= 10;
count++;
C5(n,count);
}
}
}

void C25(int n,int& count)
{
if(n >= 25)
{
while(n >= 25)
{
n -= 25;
count++;
C10(n,count);
C5(n,count);
}
}
}

void C50(int n,int& count)
{
while(n >= 50)
{
n -= 50;
count++;
C25(n,count);
C10(n,count);
C5(n,count);
}
}

void main()
{
int n;
while(cin>>n)
{
int count = 0;

if(n>=50)
{
C50(n,count);
C25(n,count);
C10(n,count);
C5(n,count);
}
else if(n>=25)
{
C25(n,count);
C10(n,count);
C5(n,count);
}
else if(n>=10)
{
C10(n,count);
C5(n,count);
}
else if(n>=5) C5(n,count);

cout<<count+1<<endl;
}
}[/cpp]
AC makes me feels good,
But WA makes me thinks hard.

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sun Dec 21, 2003 4:32 am

The time is not always the same.
Next sumbit will surely give you a suprise.
AC makes me feels good,
But WA makes me thinks hard.

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

Post by sohel » Sun Dec 21, 2003 10:55 am

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:

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sun Dec 21, 2003 2:46 pm

Thanks for your reply.
the forth step in your DP implementation make me confused.
what is coinvalue? 1,5,10,25,50?
but when j=7500
how can j+coin refers? (like S[7500+50])
AC makes me feels good,
But WA makes me thinks hard.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Dec 21, 2003 3:22 pm

what is coinvalue? 1,5,10,25,50?
yes these are the coin value.

but when j=7500
how can j+coin refers? (like S[7500+50])
the idea is S[7500+50], that is S[8000] can be made by numer of ways
S[8000] has already been made, plus the number of ways S[7500] can be made.
Because, of all the ways we made S[7500], to each if we add 50 we will get S[8000]. :wink:

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Sun Dec 21, 2003 4:00 pm

I think you're asking shouldn't S[7500 + 50] get RTE.
The answer is yes

your loop for 'j' should be something like this:

Code: Select all

for (j = 0; j + coin <= 7500; ++j)
Hope I get your question right & the answer helps.

multicast
New poster
Posts: 3
Joined: Wed Aug 13, 2003 2:24 am
Contact:

674 TLE

Post by multicast » Sun Apr 18, 2004 4:22 am

I think that the response are correct but judge replay TLE

Please someone help me
Last edited by multicast on Thu Apr 22, 2004 5:06 am, edited 1 time in total.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Apr 18, 2004 6:08 am

Hi, You should use dynamic programming to store the results in a table and then give output from the table, corresponding to an input. :wink:

multicast
New poster
Posts: 3
Joined: Wed Aug 13, 2003 2:24 am
Contact:

Please help me

Post by multicast » Sun Apr 18, 2004 11:25 pm

shamim wrote:Hi, You should use dynamic programming to store the results in a table and then give output from the table, corresponding to an input. :wink:

I know that i Should.

Can you help me to do

multicast
New poster
Posts: 3
Joined: Wed Aug 13, 2003 2:24 am
Contact:

674 - TLE - I found de bug

Post by multicast » Mon Apr 19, 2004 3:59 am

shamim,

thank you very much

I found de bug

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

674 recursion but stack overflow

Post by 58050zz » Wed Mar 02, 2005 3:27 pm

plz help

i think i can solve
but Stack Overflow

i use MS VC++
if i use ctrl+F5
run program normally(looks normally,no result)

if in debug,he say
Unheandled exception in win.exe: 0xc00000FD: Stack Overflow

i can only solve the problem under 277

i try to change 'int way' and 'int coin_mount[N]'
to long,but no use

Code: Select all


57<==input
62<==output
129
558
134
628
239
4353
277
7098

Code: Select all

#include <iostream>
#include <string>
using namespace std;
#define N 5
//#define OUTPUT 1

int Dollars(const int value[N],long coin_mount[N],
			const int &target,
			int where,long &way,int counter)
{	
	int i,gether=0,howmany=0
		,left=target;
	int amount=0;

	for(i=where;i<N;i++)
	{ 
		if(value[i]<=left && left>0 )
		{
			where=i;	//find the tail
			coin_mount[i]=left/value[i];		
			left=target%value[i];	
		}
		else
		{
			coin_mount[i]=0;
		}
	}
#ifdef OUTPUT
	for(i=0;i<N;i++)
	{
		if(coin_mount[i])
		{
			amount+=coin_mount[i]*value[i];
		}
		cout<<coin_mount[i]<<",";
	}
	cout<<" NT="<<amount;
	cout<<endl;	
#endif	

	for(int i2=where;i2>=0;i2--)
	{
		
		if(i2==N-1) 
		{
			continue;
		}
		if(coin_mount[i2])
		{
			coin_mount[i2]--;
			int target2=value[i2];
			for(int i5=i2+1;i5<N;i5++)
			{
				target2+=coin_mount[i5]*value[i5];
			}
			return Dollars(value,coin_mount,target2,i2+1,++way,0);
			//i2 is where in this recursion
		}
		else
		{
			if(i2==0 && coin_mount[0]==0)
			{
				return way+1;
			}			
		}
	}	

}

int main()
{
	//5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent.
	int value[N]={50, 25, 10 ,5,1};	
	int target=500;
	//target*=100;
	//set target as input~~
	long coin_mount[N]={0};

	while(cin>>target)
	{
			long way=0;
			  if(cin.eof()) 
				  return 0; 

	int ans=Dollars(value,coin_mount,target,0,way,0);
	cout<<ans<<endl;
	}


	return 0;
}

Post Reply

Return to “Volume 6 (600-699)”