## 674 - Coin Change

Moderator: Board moderators

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

### 674 TLE

7355<===input
way= 2001748100<===output
count= 10794898<===how many counts
7414
way= 2061906700
count= 11037473
7481
way= 2140421225
count= 11351425
7489
way= 2146113925
count= 11374075

i think i use efficiency code

but TLE

Code: Select all

``````#include <iostream>
using namespace std;

int main()
{// 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent
#define N 5
const int value[N]={1,5,10,25,50};
long way=0;
int coin_mount[N]={0};
int keyin=0;
long count=0;
int i2,i3,i7;
bool over;

do{
cin>>keyin;
if(cin.eof())
return 0;
count=0;

over=false;

int where=1;
int target=keyin;
int left=keyin;
way=0;
for(i7=0;i7<N;i7++)coin_mount[i7]=0;
do
{

int i=0;
if(left==0)
{
way++;
count++;
//output(coin_mount,value,way,count);
}

if(left)
{
coin_mount=left/value;
left=0;
way++;
count++;
//output(coin_mount,value,way,count);
}

if(coin_mount*value>=value)
{//
int temp=(coin_mount)/value;//value==1
coin_mount=target%5;
coin_mount+=temp;
way+=temp;
count++;
//output(coin_mount,value,way,count);

}

int amount=0;
for(i2=1;i2<N;i2++)
{
if(amount>=value[i2])
{
left=target;
coin_mount[i2]++;
for(i3=0;i3<N;i3++)
{
if(i3<i2)
{
coin_mount[i3]=0;
}
else if(coin_mount[i3])
{
left-=(value[i3]*coin_mount[i3]);
}

}
break;
}
else
{
amount+=value[i2]*coin_mount[i2];
}
if(i2==N-1)
{
break;
}
}

if(i2==N-1 && left==0)
{

cout<<"way= "<<way<<endl;
cout<<" count= "<<count<<endl;
break;
}

}while(true);
}while(true);
return 0;
}
``````

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

### 674 TLE

7355<===input
way= 2001748100<===output
count= 10794898<===how many counts
7414
way= 2061906700
count= 11037473
7481
way= 2140421225
count= 11351425
7489
way= 2146113925
count= 11374075

i think i use efficiency code

but TLE

Code: Select all

``````#include <iostream>
using namespace std;

int main()
{// 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent
#define N 5
const int value[N]={1,5,10,25,50};
long way=0;
int coin_mount[N]={0};
int keyin=0;
long count=0;
int i2,i3,i7;
bool over;

do{
cin>>keyin;
if(cin.eof())
return 0;
count=0;

over=false;

int where=1;
int target=keyin;
int left=keyin;
way=0;
for(i7=0;i7<N;i7++)coin_mount[i7]=0;
do
{

int i=0;
if(left==0)
{
way++;
count++;
//output(coin_mount,value,way,count);
}

if(left)
{
coin_mount=left/value;
left=0;
way++;
count++;
//output(coin_mount,value,way,count);
}

if(coin_mount*value>=value)
{//
int temp=(coin_mount)/value;//value==1
coin_mount=target%5;
coin_mount+=temp;
way+=temp;
count++;
//output(coin_mount,value,way,count);

}

int amount=0;
for(i2=1;i2<N;i2++)
{
if(amount>=value[i2])
{
left=target;
coin_mount[i2]++;
for(i3=0;i3<N;i3++)
{
if(i3<i2)
{
coin_mount[i3]=0;
}
else if(coin_mount[i3])
{
left-=(value[i3]*coin_mount[i3]);
}

}
break;
}
else
{
amount+=value[i2]*coin_mount[i2];
}
if(i2==N-1)
{
break;
}
}

if(i2==N-1 && left==0)
{

cout<<"way= "<<way<<endl;
cout<<" count= "<<count<<endl;
break;
}

}while(true);
}while(true);
return 0;
}
``````

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

### outside the loop..

I just gave a quick glance at your code and it looks like you are calculating the answers separately for every input.. and that should get TLE.

Why don't you pre-process all the answers before taking the input and then for every input, just output from the array in O(1) time.

Something like:

process();

while(1) {
take_input;
// no processing.
print_output;
}

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

### Re: outside the loop..

sohel wrote:while(1) {
take_input;
// no processing.
print_output;
}

Hope it helps. the feel of I/O is much better .
but i get
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.

Code: Select all

``````
//My inputs
int i6=0;
int input;

do{
cin>>input[i6];
if(cin.eof()||input[i6]==-1)
break;
i6++;

}while(true);
i6=-1;

//processing My code with input[i6]
do{
i6++;
if(input[i6]==-1)break;
count=0;
over=false;

int where=1;
int target=input[i6];  //set input[i6] to target and left
int left=input[i6];
way=0;
``````
i run in MS VC++
get correct and run quickly

My I/O it use 7 seconds(real world) to finish

Code: Select all

``````7026
7104
7355
7414
7481
7489
-1
1667962743
1739848682
2001748100
2061906700
2140421225
2146113925
Press any key to continue
``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
From the look of the code, it seems you are trying to solve one of the coing change problem. It can't be solved using top down( recursion) approach, you have to use bottom up Dynamic programming.

58050zz
New poster
Posts: 38
Joined: Sat Feb 26, 2005 8:13 am
shamim wrote:From the look of the code, it seems you are trying to solve one of the coing change problem. It can't be solved using top down( recursion) approach, you have to use bottom up Dynamic programming.
someone tell me dun use recursion to solve a "big number" problem

so i use for

do u mean bottom up is=>handle 1-cent. then 5 than 10...
top down=>50-cent, then 25-cent,then 10-cent, 5-cent, and 1-cent.

i use bottom up with my new code but face a new problem

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.
if u have time plz link to
http://online-judge.uva.es/board/viewtopic.php?t=4683
my code is at the bottom

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

### Re: outside the loop..

sohel wrote:
Something like:

process();

while(1) {
take_input;
// no processing.
print_output;
}

Hope it helps. i use enqueue to implement I/O
but still TLE
is it because i declare head and tail global

Code: Select all

``````#include <iostream>
#include <stdlib.h>
using namespace std;
struct node {
int data;
struct node *next;
};

struct node *tail=NULL;

void enqueue(int d)
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=d;
newnode->next=NULL;
else {
tail->next=newnode;
tail=newnode;
}
}

int dequeue()
{
int t=p->data;
free(p);
return t;
}

int main()
{// 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent
#define N 5
const int value[N]={1,5,10,25,50};
long way=0;
int coin_mount[N]={0};
int keyin=0;
long count=0;
int i2,i3,i7;
bool over;

do{
cin>>keyin;
if(cin.eof()||keyin==-1)
break;
else
{
enqueue(keyin);
}

}while(true);

do{

count=0;
over=false;
keyin=dequeue();
int where=1;
int target=keyin;
int left=keyin;
way=0;
for(i7=0;i7<N;i7++)coin_mount[i7]=0;
do
{

int i=0;
if(left==0)
{
way++;
count++;
//output(coin_mount,value,way,count);
}

if(left)
{
coin_mount=left/value;
left=0;
way++;
count++;
//output(coin_mount,value,way,count);
}

if(coin_mount*value>=value)
{//
int temp=(coin_mount)/value;//value==1
coin_mount=target%5;
coin_mount+=temp;
way+=temp;
count++;
//output(coin_mount,value,way,count);

}

int amount=0;
for(i2=1;i2<N;i2++)
{
if(amount>=value[i2])
{
left=target;
coin_mount[i2]++;
for(i3=0;i3<N;i3++)
{
if(i3<i2)
{
coin_mount[i3]=0;
}
else if(coin_mount[i3])
{
left-=(value[i3]*coin_mount[i3]);
}

}
break;
}
else
{
amount+=value[i2]*coin_mount[i2];
}
if(i2==N-1)
{
break;
}
}

if(i2==N-1 && left==0)
{

//cout<<"way= "<<way<<endl;
//cout<<" count= "<<count<<endl;
cout<<way<<endl;
break;
}

}while(true);
}while(true);

return 0;
}
``````

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### 674

Hi 58050zz,
I cant understand why u implement queue or long code for this easy problem. Actually there are 3 problems exactly like this. My code is just 10 lines. The problem is actullay Knap-sack problem. In the book CLRS, you can find the algorithm. Just implement it for those coin. At first precalculte then just print the index. Hope it helps. Good luck.
Some Love Stories Live Forever ....

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

### Re: 674

Raj Ariyan wrote:Hi
In the book CLRS, you can find the algorithm. Just implement it for those coin. At first precalculte then just print the index. Hope it helps. Good luck.
CLRS

plz tell me the full name of CLRS

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Hi,
I'm surprising to know that u still not understand abt CLRS. Actually CLRS are the first charachter of the each writer of the world famous algorithm book is "Introduction to Algorithm".

C = Cormen
L = Leiserson
R = Rivest
S = Stein

Try to read this book when u will free. It will help you much. Greedy most probably in chapter 16.
Some Love Stories Live Forever ....

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

Raj Ariyan wrote:Hi,
I'm surprising to know that u still not understand abt CLRS. Actually CLRS are the first charachter of the each writer of the world famous algorithm book is "Introduction to Algorithm".

C = Cormen
L = Leiserson
R = Rivest
S = Stein

Try to read this book when u will free. It will help you much. Greedy most probably in chapter 16.

thank you ,my Algorithm is so poor
i will get it soon and treasure it

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

### Hi 58050zz !!!

code removed... thanks!
Last edited by dovier_antonio on Fri Feb 03, 2012 10:10 am, edited 2 times in total.

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

### oh! no

Please, don't post AC codes on this forum..

-- it won't help anyone in the long run.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### ??

Hi,
I think Sohel is right. Its very bad practice to post any AC code. You can post critical input/output, some hints,any topics related with that problem but not the AC code.
Some Love Stories Live Forever ....

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

### Re: oh! no

sohel wrote:Please, don't post AC codes on this forum..

-- it won't help anyone in the long run.
not AC

is TLE

help me