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

674 TLE

Post by 58050zz » Sat Mar 05, 2005 3:11 am

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[0]=left/value[0];
			left=0;			
			way++;
			count++;
			//output(coin_mount,value,way,count);
		}		
	 


		 if(coin_mount[0]*value[0]>=value[1])
		 {//			
            int temp=(coin_mount[0])/value[1];//value[0]==1
			coin_mount[0]=target%5;
			coin_mount[1]+=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

Post by 58050zz » Sat Mar 05, 2005 3:12 am

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[0]=left/value[0];
			left=0;			
			way++;
			count++;
			//output(coin_mount,value,way,count);
		}		
	 


		 if(coin_mount[0]*value[0]>=value[1])
		 {//			
            int temp=(coin_mount[0])/value[1];//value[0]==1
			coin_mount[0]=target%5;
			coin_mount[1]+=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;
}

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

outside the loop..

Post by sohel » Sat Mar 05, 2005 6:21 am

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

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

Re: outside the loop..

Post by 58050zz » Sat Mar 05, 2005 6:52 am

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

Hope it helps. :wink:
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[200];

 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

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

Post by shamim » Sat Mar 05, 2005 8:42 am

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

Post by 58050zz » Sat Mar 05, 2005 4:18 pm

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

Post by 58050zz » Sun Mar 06, 2005 3:18 am

sohel wrote:
Something like:

process();

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

Hope it helps. :wink:
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 *head=NULL;
struct node *tail=NULL;

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

int dequeue()
{
	if (head==NULL) return -1;
	struct node *p=head;
	head=head->next;;
	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{
		
   if(head==NULL)return 0;
 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[0]=left/value[0];
			left=0;			
			way++;
			count++;
			//output(coin_mount,value,way,count);
		}		
	 


		 if(coin_mount[0]*value[0]>=value[1])
		 {//			
            int temp=(coin_mount[0])/value[1];//value[0]==1
			coin_mount[0]=target%5;
			coin_mount[1]+=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

Post by Raj Ariyan » Tue Mar 08, 2005 3:33 pm

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

Post by 58050zz » Tue Mar 08, 2005 4:28 pm

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

About CLRS

Post by Raj Ariyan » Tue Mar 08, 2005 5:34 pm

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

Re: About CLRS

Post by 58050zz » Tue Mar 08, 2005 5:47 pm

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

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

Hi 58050zz !!!

Post by dovier_antonio » Sun Mar 13, 2005 11:32 am

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

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

oh! no

Post by sohel » Sun Mar 13, 2005 1:48 pm

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

??

Post by Raj Ariyan » Sun Mar 13, 2005 3:00 pm

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

Post by 58050zz » Mon Mar 14, 2005 6:14 am

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

Post Reply

Return to “Volume 6 (600-699)”