BISHOPS problem SPOJ

spoj

#1

I am trying to solve Bishops problem on SPOJ. I am getting a TLE. There are actually 3 for loops effectively which on maximum runs for 100 times, even though TLE!!! Can some one point out inefficient part of the code?

Edit: I optimized the code as shown below. This time no function calls etc… but TLE!! I have solved this question using Java, Python. I really want to implement this using C++. Any help would be appreciated. Thanks!!

/Earlier code/


#include  
#define si(a) scanf("%d",&a)
#define nl printf("
")
#define ULL unsigned long long
//set sx, sy;
using namespace std;

int A[101];
char ans[100];
int l;  
void done(int i){
	if(!A*){
	  A*=9;
	  ans[l-i-1]=A*+'0';
	  done(i+1);
	}
	else {
		A*--;
		ans[l-i-1]=A*+'0';
	}
}

int main()
{
   
   int i;
   char P[100]={0};
   while(scanf("%s",P)!=0){
   	int c=0,x;
   	memset(A,0,100);
   	memset(ans,0,100);
   	l=strlen(P);
	   for(i=l-1;i>=0;i--){
	   	A[l-i-1]=P*-'0';	
	   }
	   for(i=0;i=2){
	   	A[0]=A[0]-2;
	   	ans[l-1]=A[0]+'0';
	   }
	   else {
	   	A[0]=A[0]+10-2;
	   	ans[l-1]=A[0]+'0';
	   	done(1);
	   }
	   if(c)printf("%d",c);
	   puts(ans);
	   nl;		
   }
   return 0;   
}


/*optimized code*/
  
#include
#define si(a) scanf("%d",&a)

//set sx, sy;
using namespace std;

int A[101];
char ans[100];
int l;

int main()
{
   
   int i;
   char P[100]={0};
   while(scanf("%s",P)!=0){
   	int c=0,x;
   	memset(A,0,100);
   	memset(ans,0,100);
   	l=strlen(P);
	   for(i=l-1;i>=0;i--){
	   	A[l-i-1]=P*-'0';	
	   }
	   A[l-1]--;
	   for(i=0;i<l;i++){
	   	x=A*;
	   	if(i<l-1)x+=9;
	   	x=2*x+c;
	   	A*=x%10;
	   	ans[l-i-1]=A*+'0';
	   	c=x/10;
	   }
	   
	   if(c)printf("%d",c);
	   puts(ans);
	   printf("
");		
   }
   return 0;   
}


#2

You are running 2 for loops inside a while loop and if all runs for a maximum no. of times(as you say 100) the total no. of iterations will be equal to=100*(100+100) i.e. 20000. Moreover you are using a function call inside the loop which is i guess consuming a lot of time to transfer the control. Think of calling a recursive function(as u are using recursive fxn) 100 times, it really consumes much time. Try using inline function instead.