## 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
Thank you and good luck! 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
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:
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. Also, you should change "long m" to "long m".

Good luck! Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia
My code is wrong Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### 674 TLE

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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 = 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. Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China
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.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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 can be made by numer of ways
S has already been made, plus the number of ways S can be made.
Because, of all the ways we made S, to each if we add 50 we will get S. Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh
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

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.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Hi, You should use dynamic programming to store the results in a table and then give output from the table, corresponding to an input. multicast
New poster
Posts: 3
Joined: Wed Aug 13, 2003 2:24 am
Contact:

### Please help me

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

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

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)
{
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;
}
``````