Page 3 of 6

674 TLE

Posted: Sat Mar 05, 2005 3:11 am
by 58050zz
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;
}

674 TLE

Posted: Sat Mar 05, 2005 3:12 am
by 58050zz
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;
}

outside the loop..

Posted: Sat Mar 05, 2005 6:21 am
by sohel
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:

Re: outside the loop..

Posted: Sat Mar 05, 2005 6:52 am
by 58050zz
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

Posted: Sat Mar 05, 2005 8:42 am
by shamim
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.

Posted: Sat Mar 05, 2005 4:18 pm
by 58050zz
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

Re: outside the loop..

Posted: Sun Mar 06, 2005 3:18 am
by 58050zz
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;
}

674

Posted: Tue Mar 08, 2005 3:33 pm
by Raj Ariyan
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.

Re: 674

Posted: Tue Mar 08, 2005 4:28 pm
by 58050zz
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

About CLRS

Posted: Tue Mar 08, 2005 5:34 pm
by Raj Ariyan
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.

Re: About CLRS

Posted: Tue Mar 08, 2005 5:47 pm
by 58050zz
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

Hi 58050zz !!!

Posted: Sun Mar 13, 2005 11:32 am
by dovier_antonio
code removed... thanks!

oh! no

Posted: Sun Mar 13, 2005 1:48 pm
by sohel
Please, don't post AC codes on this forum..

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

??

Posted: Sun Mar 13, 2005 3:00 pm
by Raj Ariyan
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.

Re: oh! no

Posted: Mon Mar 14, 2005 6:14 am
by 58050zz
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