OJ Board

Posted: **Sun Mar 25, 2007 7:26 am**

hmm now i got AC.
thanx everybody.

      Deleted !

newton......................... simply the best

Posted: **Sun Mar 25, 2007 8:09 am**

Code: Select all

char* x;

'x' is just a pointer not an array.. so you can't copy some data on it like this..

Code: Select all

strcpy(x,"1");

This is an invalid memory reference..

And another BIG mistake is..

Code: Select all

return tem;

'tem' is a temporary variable.. so when you leave the function, the memory area for 'tem' will be freed..

Code: Select all

x = str_mul(x,n);

So, It is not guarranted that 'x' has the value which you want..
Even though your code works for some cases, it's a very dangerous program..

Posted: **Sun Mar 25, 2007 3:38 pm**

I unable to understand Why I am getting WA?
Can Any genious programmer help me telling what's the cause?

code removed after AC
thanks

Posted: **Sun Mar 25, 2007 4:51 pm**

Your 'str_rev' function is not ok. Factorial(4) = 24.

Replace the following line

Code: Select all

for(i = 0; i <= len / 2; i++)

with

Code: Select all

for(i = 0; i < len / 2; i++)

Hope you get accepted.

Posted: **Wed Mar 28, 2007 1:10 pm**

Only for this I am getting WA.
Now I got AC.
Thanks for reply.

Posted: **Wed Mar 28, 2007 3:37 pm**

Why TLE.anyone can help me?
#include<iostream.h>

int main(){
int i,j,k,n,c=0,l,m,s;

while(cin>>n){
if((n==1)||(n==0))
{ cout<<n<<"!"<<endl<<'1';}

else{
int a[100000]={-1};

i=99999;
j=n*(n-1);
while(j>9){
k=j%10;
a=k;
j=j/10;
i--;}
a=j;
for(l=n-2;l>=2;l--){
for(j=99999;j>=i;j--){
k=c+l*a[j];
s=j;
m=k%10;
a[s]=m;
k=k/10;
c=k;}
while(c>9){
m=c%10;
s--;
a[s]=m;
c=c/10;}
if(c>0){
s--;
a[s]=c;}
if(i>s) i=s;
c=0;}
cout<<n<<"!"<<endl;
for(l=i;l<100000;l++)
cout<<a[l];}
cout<<endl;
}
return 0;}

Posted: **Thu Mar 29, 2007 11:40 am**

Your code is difficult to follow, but it seems that you are not preprocessing the results. You must generate the factorials before taking any input.

Posted: **Mon Apr 16, 2007 10:26 pm**

Search your problem first. Don't open a new thread if there is one already.

Posted: **Fri Jun 15, 2007 1:06 pm**

can any body help me.

i get TLE.

Code: Select all

#include <iostream>
#include <string>

using namespace std;

string s[1001];
bool ss[1001]={0};


struct f_t
{
 long long a[401];
 short int ptr;
};

f_t fact[1001];


long long power()
{
     long long q=1;
     for(int i=0;i<15;i++)
     q*=10;
     return q;
}


void f(int n,f_t f)
{
     long long q=0;
     int i;
     for(i=400;i>f.ptr;i--)
     {
     q+=n*f.a[i];
     fact[n].a[i]=q%power();
     q/=power();
     }
     while(q!=0)
     {
     fact[n].a[i]=q%power();
     q/=power();
     i--;
     }
     fact[n].ptr=i;
}     

string sum(string s1,string s2)
{
       int ptr1=s1.length()-1;
       int ptr2=s2.length()-1;
       int q=0;
       char a;
       string res;
       while(ptr1!=-1 || ptr2!=-1)
       {
        if(ptr1>=0 && ptr2>=0)
        {
                   q+=(s1[ptr1]-'0')+(s2[ptr2]-'0');
                   ptr1--;
                   ptr2--;
        }
        else
        if(ptr1==-1 && ptr2>=0)
        {
                   q+=s2[ptr2]-'0';
                   ptr2--;
        }
        else
        if(ptr1>=0 && ptr2==-1)
        {
                   q+=s1[ptr1]-'0';
                   ptr1--;
        }
        a=(q%10+'0');
        res=a+res;
        q=q/10;
       }
       if(q!=0)
       res=(char)(q+'0')+res;
       return res;
}



string sum1(long long a[],int ptr)
{
 string s2="0";
 string s1;
 int tv=0;
 for(int i=400;i>ptr;i--)
 {
 s1="";
 while(a[i]!=0)
 {
 s1=(char)(a[i]%10+'0')+s1;
 a[i]/=10;
 }
 for(int j=0;j<tv;j++)
 s1+='0';
 tv+=15;
 s2=sum(s1,s2);
 }
 return s2;
}



int main()
{
    int n;
    fact[0].a[400]=1;
    fact[0].ptr = 399;
    s[0]="1";
    for(int i=1;i<=1000;i++)
            f(i,fact[i-1]);
    
    while(cin>>n)
    {
    cout<<n<<'!'<<endl;
    if(!ss[n])
     s[n]=sum1(fact[n].a,fact[n].ptr);
    ss[n]=1;
    cout<<s[n]<<endl;
    }
    return 0;
}

thank u.

Posted: **Fri Jun 15, 2007 1:20 pm**

can any body help me.
i get TLE.

Code: Select all

#include <iostream>
#include <string>

using namespace std;

string s[1001];
bool ss[1001]={0};


struct f_t
{
 long long a[401];
 short int ptr;
};

f_t fact[1001];


long long power()
{
     long long q=1;
     for(int i=0;i<15;i++)
     q*=10;
     return q;
}


void f(int n,f_t f)
{
     long long q=0;
     int i;
     for(i=400;i>f.ptr;i--)
     {
     q+=n*f.a[i];
     fact[n].a[i]=q%power();
     q/=power();
     }
     while(q!=0)
     {
     fact[n].a[i]=q%power();
     q/=power();
     i--;
     }
     fact[n].ptr=i;
}     

string sum(string s1,string s2)
{
       int ptr1=s1.length()-1;
       int ptr2=s2.length()-1;
       int q=0;
       char a;
       string res;
       while(ptr1!=-1 || ptr2!=-1)
       {
        if(ptr1>=0 && ptr2>=0)
        {
                   q+=(s1[ptr1]-'0')+(s2[ptr2]-'0');
                   ptr1--;
                   ptr2--;
        }
        else
        if(ptr1==-1 && ptr2>=0)
        {
                   q+=s2[ptr2]-'0';
                   ptr2--;
        }
        else
        if(ptr1>=0 && ptr2==-1)
        {
                   q+=s1[ptr1]-'0';
                   ptr1--;
        }
        a=(q%10+'0');
        res=a+res;
        q=q/10;
       }
       if(q!=0)
       res=(char)(q+'0')+res;
       return res;
}



string sum1(long long a[],int ptr)
{
 string s2="0";
 string s1;
 int tv=0;
 for(int i=400;i>ptr;i--)
 {
 s1="";
 while(a[i]!=0)
 {
 s1=(char)(a[i]%10+'0')+s1;
 a[i]/=10;
 }
 for(int j=0;j<tv;j++)
 s1+='0';
 tv+=15;
 s2=sum(s1,s2);
 }
 return s2;
}



int main()
{
    int n;
    fact[0].a[400]=1;
    fact[0].ptr = 399;
    s[0]="1";
    for(int i=1;i<=1000;i++)
            f(i,fact[i-1]);
    
    while(cin>>n)
    {
    cout<<n<<'!'<<endl;
    if(!ss[n])
     s[n]=sum1(fact[n].a,fact[n].ptr);
    ss[n]=1;
    cout<<s[n]<<endl;
    }
    return 0;
}

thank u.

Posted: **Fri Jun 15, 2007 2:45 pm**

There is no need to post the same question more than once.

Your approach is very complex. I haven't studied your code in detail, apart from observing that it's too slow. I suggest you go for a much simpler approach, as described below.

One bug:

Code: Select all

if(!ss[n]) {
     s[n]=sum1(fact[n].a,fact[n].ptr); 
    ss[n]=1;
}

You forgot the braces around these instructions, so results weren't cached. However, this is not enough to run all numbers from 1 to 1000 in time.

Tip: Make a subroutine that multiplies a string with an integer by operating directly on the string. Then, precalculate the answers. Build up an array of 1001 strings, calculating n! based on (n-1)!. Then, read all the input and print the answer.

Posted: **Thu Dec 04, 2008 11:43 am**

Tried a lot but getting TLE.
Here is my code

Code: Select all

[b]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define M 3000

void BigMul(char *s1, char*s2, char *result);
void string_filter(char *s1, char*s2);
void Bigsum (char *str1,char *str2, char *sum);
void Rev(char *s);
void myitoa(int res , char *s);

int main(void)
{

	int n,i;
	char result[M],s1[M],s2[M];

	//scanf("%s %s",s1,s2);

	while( scanf("%s",s1)!=EOF)
	{
		n=atoi(s1);
		if(n==0 || n==1)
		{
			printf("%d!\n",n);
			printf("1\n");
			continue;
		}
		strcpy(s2 , "1");
		for(i=1; i<=n; i++)
		{
			myitoa(i , s1);
			BigMul(s1, s2, result);
			strcpy(s2 , result);
		}
		printf("%d!\n",n);
		printf("%s\n",result);
		//printf("\n\n%d\n\n", strlen(result));
	}

}



void BigMul(char *s1, char*s2, char *result)
{
	char temp[M], res[M],n1[M],sum[M];
	int a,b,i,k,carry=0,j,x,n,cross;

	//string_filter(s1 , s2);

	if(s1[0]=='\0' || s2[0]=='\0')
	{
		strcpy(result,"0");
	}
	else
	{

		a=strlen(s1);
		b=strlen(s2);

		if(a < b)
		{
			strcpy(temp,s1);
			strcpy(s1,s2);
			strcpy(s2,temp);
			a=strlen(s1);
			b=strlen(s2);
		}
		cross=0;

		for(j=b-1; j>=0; j--)
		{
			if(cross>=1)
			{
				for(k=0; k<cross; k++)
					n1[k]='0';
			}
			else
				k=0;
			carry=0;

			for(i=a-1; i>=0; i--,k++)
			{
				x=(((s2[j]-'0')*(s1[i]-'0'))+carry)%10;
				n1[k]=x+'0';
				carry=(((s1[i]-'0')*(s2[j]-'0'))+carry)/10;
			}
			if(carry)
				n1[k++]=carry+'0';
			n1[k]='\0';

			if(cross==0)
			{
				for(n=0; n<k; n++)
					sum[n]='0';
				sum[n]='\0';
				Rev(sum);
			}
			Rev(n1);
			//puts(n1);
			//strcpy(str1,n1);
			Bigsum(n1 , sum , res);
			strcpy(sum,res);
			cross++;
		}

		strcpy(result, sum);
	}

}

void string_filter(char *s1, char*s2)   //removing leading zeros
{
	int i,j,k;
	char temp[M];

	for(i=0; s1[i]=='0'; i++);
	for(j=i,k=0; s1[j]; j++)
		temp[k++]=s1[j];

	temp[k]='\0';
	strcpy(s1,temp);

	for(i=0; s2[i]=='0'; i++);
	for(j=i,k=0; s2[j]; j++)
		temp[k++]=s2[j];

	temp[k]='\0';
	strcpy(s2,temp);
	

}


/*
void BigSum (void)
{
	char   ans[1000]   ;
	int carry=0, i , x ,j,m=0  ;
	i=strlen(str1)-1;
	j=strlen(sum)-1;

	while(i>=0 && j>=0)
	{
		x=str1[i]-'0'+sum[j]-'0'+carry;
		ans[m]=(x%10)+'0' ;
		carry = (x/10) ;
		m++;
		i--;
		j--;
	}

	if(j==-1)
	{
		while(i>=0)
		{
			x=str1[i]-'0'+carry ;
			ans[m++]=(x%10) +'0' ;
			carry=(x/10);
			i--;
		}
	}
	else
	{
		while(j>=0)
		{
			x=sum[j]-'0'+carry ;
			ans[m++]=(x%10) +'0' ;
			carry=(x/10);
			j--;
		}
	}

	if(carry)
	{
		ans[m++]=carry+'0' ;
		ans[m]='\0' ;
	}
	else
		ans[m]='\0';

	strrev(ans);
	strcpy(sum,ans);
	
}*/


void Bigsum (char *str1,char *str2, char *sum)
{
	char   ans[M]   ;
	int carry=0, i , x ,j,m=0  ;
	i=strlen(str1)-1;
	j=strlen(str2)-1;

	while(i>=0 && j>=0)
	{
		x=str1[i]-'0'+str2[j]-'0'+carry;
		ans[m]=(x%10)+'0' ;
		carry = (x/10) ;
		m++;
		i--;
		j--;
	}

	if(j==-1)
	{
		while(i>=0)
		{
			x=str1[i]-'0'+carry ;
			ans[m++]=(x%10) +'0' ;
			carry=(x/10);
			i--;
		}
	}
	else
	{
		while(j>=0)
		{
			x=str2[j]-'0'+carry ;
			ans[m++]=(x%10) +'0' ;
			carry=(x/10);
			j--;
		}
	}

	if(carry)
	{
		ans[m++]=carry+'0' ;
		ans[m]='\0' ;
	}
	else
		ans[m]='\0';

	Rev(ans);
	strcpy(sum,ans);
	
}


void Rev(char *s)
{
	char temp[M];
	int i,j=0;

	for(i=strlen(s)-1; i>=0; i--,j++)
	{
		temp[j]=s[i];
	}
	temp[j]='\0';
	strcpy(s,temp);

}


void myitoa(int res , char *s)
{
	int i=0,r,j=0;
	char temp[M];

	if(res==0)
	{
		s[0]='0'; s[1]='\0';
	}
	else
	{
		for(i=0; res!=0; i++)
		{
			r=res % 10;
			s[i]=r+'0';
			res=res/10;
		}
		s[i]='\0' ;
	

		for(i=strlen(s)-1; i>=0; i--,j++)
		{
			temp[j]=s[i];
		}
		temp[j]='\0';
		strcpy(s,temp);

	}
	
}
[/b]

Posted: **Thu Dec 04, 2008 4:34 pm**

You shouldn't re-compute factorials when processing each input case, that's too slow.
First, compute a table with values of all 1000 factorials, and for each input print the string from that table.

Posted: **Fri May 01, 2009 1:16 pm**

Can anyone tell me why i got runtime error?
I run in my computer is ok

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i=2,n,ans[100000]={0},rans[1000][2600]={0,0},x=1,time,num,j,len[100000]={0};
    len[0]=1;
    ans[0]=1;
    while (i<=1000)
     {
         x=product(ans,i,x);

         for(j=0;j<=x;j++)
         {
          rans[i][j]=ans[j];
         }
         i++;
         len[i]=x+2;
     }
    while(scanf("%d",&n)!=EOF)
    {


       while(rans[n][len[n]]==0)
        len[n]--;

     for (i=len[n];i>=0;i--)
     {
         printf("%d",rans[n][i]);

     }
     printf("\n");
    }
    return 0;
}
int product(int *ans,int n,int lans)
{
    int i,j,fln,num[100000]={0},lnum=0,bot,tmp[100000]={0};

    for (i=0;n!=0;i++)
    {
        num[i]=n%10;
        n=n/10;
        lnum++;
    }
    for (i=0;i<lans;i++)
    {
        for (j=0;j<lnum;j++)
        {
            bot=ans[i]*num[j];

            tmp[i+j]+=bot;
            if(tmp[i+j]>=10)
            {
                tmp[i+j+1]+=tmp[i+j]/10;
                tmp[i+j]=tmp[i+j]%10;
            }

        }
    }

    for (i=lnum*lans+1;;i--)
    {
        if (tmp[i]!=0 || i==0)
        {
            fln=i+1;
            break;
        }
    }
    for (i=0;i<(lans+5);i++)
    {
     ans[i]=tmp[i];
    }


    return fln;
}

Posted: **Sun Sep 13, 2009 10:52 am**

peterwen1990 wrote:Can anyone tell me why i got runtime error?
I run in my computer is ok

Its easy ?

rans[1000][2600];
while (i<=1000){
rans[j]=ans[j];
}

why should't this get RunTime error ??

OJ Board

623 - 500!

623

can any body help me.

TLE

623 ::: TLE , Need Help.

Re: 623 - 500!

Re: 623 - 500!

Re: 623 - 500!