674  Coin Change
Moderator: Board moderators

 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.

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

 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[7489]" to "long m[7490]".
Good luck!
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[7489]" to "long m[7490]".
Good luck!

 New poster
 Posts: 6
 Joined: Mon Dec 01, 2003 5:16 pm
 Location: Orenburg, Russia
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]
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.
But WA makes me thinks hard.
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.
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.
yes these are the coin value.what is coinvalue? 1,5,10,25,50?
the idea is S[7500+50], that is S[8000] can be made by numer of waysbut when j=7500
how can j+coin refers? (like S[7500+50])
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].

 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:
Hope I get your question right & the answer helps.
The answer is yes
your loop for 'j' should be something like this:
Code: Select all
for (j = 0; j + coin <= 7500; ++j)
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
674  TLE  I found de bug
shamim,
thank you very much
I found de bug
thank you very much
I found de bug
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
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==N1)
{
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: 50cent, 25cent, 10cent, 5cent, and 1cent.
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;
}