623 - 500!

[Lon]

help!!!
TLE!!!!
who can tell me why TLE????
thank you!!

this is my code
/* @JUDGE_ID: ******* 623 C++ */
#include<string.h>
#include<stdio.h>
long int in,i,k,j=0,x;
long int num[2600];
void clearzero()
{
num[0]=1;
for(i=1;i<=2600;i++)
num=0;
}
int cal(int af)
{
for(i=0;i<=j;i++)
{
if(num!=0)
num*=n;
}
}
void carry()
{
for(i=0;i<=j;i++)
{
if(num>9)
{
while(num>9)
{
x=num/10;
num [i+1]+=x;
num%=10;
}
if(i==j)
{
if(i+1>j)
j=i+1;
}
}
}
}
void main()
{
int fa;
clearzero();
while(scanf(" %ld",&in)==1)
{
fa=in; j=0;
num[0]=1;
for(;fa>0;fa--)
{
cal(fa);
carry();
}
printf("%ld!\n",in);
for(i=j;i>=0;i--)
{
printf("%ld",num);
num=0;
}
printf("\n");
}
}

[Lon]

sorry I post wrong code!!
this is true!!
/* @JUDGE_ID: 19805FE 623 C++ */
#include<string.h>
#include<stdio.h>
long int in,i,k,j=0,x,fa;
long int num[2600];
void clearzero()
{
num[0]=1;
for(i=1;i<=2600;i++)
num=0;
}
int cal(int fa)
{
for(i=0;i<=j;i++)
{
if(num!=0)
num*=fa;
}
}
void carry()
{
for(i=0;i<=j;i++)
{
if(num>9)
{
while(num>9)
{
x=num/10;
num [i+1]+=x;
num%=10;
}
if(i==j)
{
if(i+1>j)
j=i+1;
}
}
}
}
void main()
{
int fa;
clearzero();
while(scanf(" %ld",&in)==1)
{
fa=in; j=0;
num[0]=1;
for(;fa>0;fa--)
{
cal(fa);
carry();
}
printf("%ld!\n",in);
for(i=j;i>=0;i--)
{
printf("%ld",num);
num=0;
}
printf("\n");
}
}

[Zhao Le]

who can tell me why TLE????

why you got TLE, it is obvious.( though I got that TLE not very long time ago.)

hint:
you should use DP to solve the problem.

Do a single test :
i=0;
while(i<1000)//even larger I guess in OJ
calculate(1000);//calculate 1000!

see how long it will get you out.

and deleted the first post.!!!

[Frostina]

Sorry, I'm so stupid......||||

0! = 1 ...>"<

[Zhao Le]

Sorry, I'm so stupid......||||

0! = 1 ...>"<

There is nothing to blame.

Practice more you will get the problem solved quick.

[AaronWu]

Yes,that's the trick I've been stumped for a long time.Now,I pass it too.
We should be more careful when solving this kind of problem.

[Acetik]

[c]/* @JUDGE_ID: 43187ZH 623 C "NADA" */
#include <stdio.h>
#define TAILLE_TAB 5000

void toTab( int nb , int* tab)
{
unsigned i;

for( i = 0 ; nb >= 1 ; i++ )
{
tab = nb % 10;
nb /= 10;
}

}

void initialiser( int* tab )
{
unsigned i;
for( i = 0 ; i < TAILLE_TAB ; i++ )
tab = -1;
}

void afficher( int* tab )
{
unsigned i;

for( i = TAILLE_TAB ; i > 0; i--)
if( tab[i-1] >= 0)
printf("%d",tab[i-1]);
printf("\n");
}

void multiplier( int* tab1, int* tab2)
{
/* le r

[Subeen]

apply dynamic programming here:

1. first store all the answers in a table ( here two dimensional array )
2. just read input and write output

see that, if you calculate factorial of n then you must calculate factorials of 1 to n-1, hope it will help

[SePulTribe]

Hey I've been toggling between WA and TLE on this question and it's driving me nuts!! *Pulls my hair out. Please help! Thanks loads.

[c]#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXLEN 999999

typedef struct
{
char num[MAXLEN];
long length;
} bignum;


void shiftright(bignum *a)
{
long ii;
a->length++;
for (ii = a->length; ii > 0; ii--)
{
a->num[ii] = a->num[ii-1];
}
a->num[0] = 0;
}

void int_to_bignum(long i, bignum *b)
{
long index = 0;
while (i > 0)
{
b->num[index++] = i % 10;
i /= 10;
}
b->length = index;
}

void remzer(bignum *a)
{
long ii;
for (ii = a->length - 1; ii >= 0; ii--)
{
if (a->num[ii] != 0)
return;
a->length--;
}
}
void init_bignum(bignum *a)
{
long ii;
a->length = 0;
memset(a->num, 0x0, sizeof(char) * MAXLEN);
}


void add(bignum a, bignum b, bignum *c)
{
long ii, len, carry = 0;
len = (a.length > b.length) ? a.length : b.length;
len++;
c->length = len;
for (ii = 0; ii < len; ii++)
{
c->num[ii] = (carry+a.num[ii]+b.num[ii]) % 10;
carry = (carry+a.num[ii]+b.num[ii]) / 10;
}
remzer(c);
}

void multiply(bignum a, bignum b, bignum *c)
{
bignum temp;
long ii, jj, zz, carry;
init_bignum(c);
c->length = 1;
for (ii = 0; ii < b.length; ii++)
{
carry = 0;
init_bignum(&temp);
for (jj = 0; jj < a.length; jj++)
{
temp.num[jj] = (carry + a.num[jj] * b.num[ii]) % 10;
carry = (carry + a.num[jj] * b.num[ii]) / 10;
temp.length++;
}
if (carry != 0)
{
temp.num[jj] = carry;
temp.length++;
}
for (zz = 0; zz < ii; zz++)
shiftright(&temp);
add(*c, temp, c);
}
}

int main()
{
bignum result, temp1;
long temp, te, ii, jj, digits;

te = -1;
while (scanf("%d\n", &temp) != EOF)
{
if (temp != te)
{
init_bignum(&temp1);
if (temp < te)
init_bignum(&result);
int_to_bignum(1, &result);
for (ii = ((temp < te) ? 2 : (te + 1)); ii <= temp; ii++)
{
int_to_bignum(ii, &temp1);
multiply(result, temp1, &result);
}
}
printf("%d!\n", temp);
for (jj = result.length - 1; jj >= 0; jj--)
printf("%d", result.num[jj]);
printf("\n");
te = temp;
}
return 0;
}
[/c]

[Ghust_omega]

Hi !! SePulTribe in this problem try to precalculate the values in this form you can avoid the TLE and maybe the WA
Hope it Helps
Keep posting !!

[SePulTribe]

Yeah I was thinking of precalculation too but, if 500! has 1000 digits, precalculation will take up too much memory!

[WR]

You'll need about 11 MB which is ok with the Online Judge.

[SePulTribe]

Umm there's a probem with that.My code is now 1.1MB! And the judge has a limit of 40KB on source code. My code works perfectly fast though. Haha.

[Ghust_omega]

Hi !! SePulTribe my source code is 4.5K and the precalculated values is in runtime, I mean this :

Code: Select all

CUT

I think That I say everithing for solved this problem sorry and when you get AC tell me for quit this code ....
Hope it helps
Keep posting !!

[SePulTribe]

Hey!!! Thanks so much for your help! I followed exactly what you said and true enough I got AC for it. And my code is amazingly fast. I tried it on my comp with an input file containing the numbers 0 to 1000 and it took only about 6 seconds. Anyways, my prog took up 2942 KB of memory. Haha this has got to be the most memory-expensive competitive program I've ever written. Thanks a lott!!!!