623 - 500!

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

Lon
New poster
Posts: 7
Joined: Sat Jan 31, 2004 12:55 pm

623 TLE !!!! Help PLZ!!!!

Post by Lon » Sat Jan 31, 2004 1:05 pm

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");
}
}
my name is Lon

Lon
New poster
Posts: 7
Joined: Sat Jan 31, 2004 12:55 pm

Post by Lon » Sat Jan 31, 2004 1:09 pm

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");
}
}
my name is Lon

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sat Jan 31, 2004 4:04 pm

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

and deleted the first post.!!!
AC makes me feels good,
But WA makes me thinks hard.

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

623

Post by Frostina » Sun Feb 01, 2004 8:57 am

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

0! = 1 ...>"<
Thanks for your help ! ;)

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sun Feb 01, 2004 1:05 pm

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

0! = 1 ...>"<
There is nothing to blame.

Practice more you will get the problem solved quick.
AC makes me feels good,
But WA makes me thinks hard.

AaronWu
New poster
Posts: 14
Joined: Sat May 10, 2003 4:21 am

Post by AaronWu » Tue Feb 10, 2004 12:16 pm

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. :lol:
To save time is to lengthen life.

Acetik
New poster
Posts: 1
Joined: Thu Mar 18, 2004 10:50 pm

623 : TLE

Post by Acetik » Thu Mar 18, 2004 10:52 pm

[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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Fri Mar 19, 2004 8:32 am

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
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

623 Help!!!

Post by SePulTribe » Thu Dec 02, 2004 8:05 pm

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]

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Dec 03, 2004 3:07 am

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
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Post by SePulTribe » Fri Dec 03, 2004 7:55 am

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

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Fri Dec 03, 2004 2:14 pm

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

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Post by SePulTribe » Fri Dec 03, 2004 5:59 pm

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.

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Sat Dec 04, 2004 12:42 am

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 !!
Last edited by Ghust_omega on Sat Dec 04, 2004 8:54 pm, edited 1 time in total.

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Post by SePulTribe » Sat Dec 04, 2004 5:12 pm

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

Post Reply

Return to “Volume 6 (600-699)”