623 - 500!

[idler]

Without pre-calculate, how to solve this problem in 0.000 seconds?

[idler]

This is my code (C, 0.010 seconds)

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

#define MODULE_NUM 1000000L
#define LTYPE unsigned int
#define MAX_SIZE 193
#define MAX_N 500

typedef struct
{
unsigned char size;
LTYPE l[MAX_SIZE];
} big;

/* Global variables */
big *g_save_num[MAX_N + 1];
unsigned char g_saved[MAX_N + 1];

/* Basic functions */
void init_big(big *n)
{
n->size = 0;
memset(n->l, 0, sizeof(n->l));
}

void set_big_u(big *a, LTYPE b)
{
a->size = 1;
a->l[0] = b;
}

void multi_big_u(big *a, LTYPE b, big *c)
{
unsigned char i;
LTYPE tmp = 0;
LTYPE cur = 0;

for (i = 0; i < a->size; i++)
{
cur = b * (a->l) + tmp;
c->l = cur % MODULE_NUM;
tmp = cur / MODULE_NUM;
}

i = a->size; /* Can be omitted? */
while (tmp > 0)
{
c->l = tmp % MODULE_NUM;
tmp = tmp / MODULE_NUM;
i++;
}
c->size = i;
}

void copy_big(big *a, const big *b)
{
memcpy(a, b, sizeof(big));
}

void print_limb(LTYPE n)
{
/* While MODULE_NUM == 1000000L */
if (n < 100000) printf("0");
if (n < 10000) printf("0");
if (n < 1000) printf("0");
if (n < 100) printf("0");
if (n < 10) printf("0");
printf("%u", n);
}

void print_big(big *a)
{
int i;

printf("%u", a->l[a->size - 1]);
for (i = a->size - 1; i > 0; i--) print_limb(a->l);
}

/* Main part */
void init()
{
int i;

memset(g_saved, 0, sizeof(g_saved));
for (i = 1; i < MAX_N + 1; i++)
{
g_save_num = malloc(sizeof(big));
init_big(g_save_num);
}
}

void solve()
{
int i, j;
LTYPE n;
big *a;

a = malloc(sizeof(big));

while (scanf("%u", &n) > 0)
{
/* Search the nearest result */
i = n;
while ((i > 0) && (g_saved == 0)) i--;
if (i == 0)
{
init_big(a);
set_big_u(a, 1);
}
else
copy_big(a, g_save_num);

i++;
for (j = i; j <= (int)n; j++) multi_big_u(a, j, a);

/* Save results */
g_saved[n] = 1;
copy_big(g_save_num[n], a);

printf("%u!n", n);print_big(a); printf("n");
}
}

int main()
{
init();
solve();

return 0;
}

[zsepi]

hei,

my problem isn't specificly just with the 500! problem, but with output in general, though this is the last prog I got stucked with. Whenever I get into a problem, I get the algorythm right and then I spend amazingly long time on trying to figure out the exact output format required by the judge. And in this particular example I particularly fail on the nth attempt even.

could someone help me with the output? I use the code (C++):
cout << number << "!" << endl;
cout << factorialString << endl;

and it doesn't work, though that's what th output should look like...

thanks in advance, your help is really appreciated!

peter

PS: the code is giving the right factorial values, it's not the problem...[/cpp]

[arc16]

hmmm, sometimes it's about how to READ the input, not to write it. You know, the input could be ugly for some problem, lot of blank space, empty line, etc etc etc.

[zsepi]

thanks for the reply, but i do read the whole thing well... on my computerscreen the output looks exactly like it does on the webpage, but it is rejected... probably the badly placed __ endl __ is the problem, but i tried a lot of different combinations.... :(

[b3yours3lf]

I try to solved problem 623 but I got WA.
I can find my mistake.
This is my source code.
[c]#include<stdio.h>

void main(void)
{
int arr[1135];
int fak,i,j;
int temp,borrow=0;
/*freopen("623.in","r",stdin);
freopen("623.out","w",stdout);*/

while(scanf("%d",&fak)==1)
{
if(fak==0)
{
printf("%d!\n",fak);
printf("1");
}
else
{
for(i=0;i<1135;i++) arr=0;
arr=1;
for(i=1;i<=fak;i++)
{
for(j=1134;j>=0;j--)
{
temp=(arr[j]*i)+borrow;
if(temp>=10)
{
arr[j]=temp%10;
borrow=temp/10;
}
else
{
arr[j]=temp;
borrow=0;
}
}
arr[j]=borrow;
borrow=0;
}
i=0;
while(arr==0) i++;
printf("%d!\n",fak);
j=1;
for(;i<1135;i++)
{
printf("%d",arr);
if(j%80==0) printf("\n");
j++;
}
printf("\n");
}
}
}
[/c]

[ec3_limz]

In this problem, you should print out the required output number on ONE SINGLE LINE regardless of how long it is. If you don't believe me, check out http://acm.uva.es/p/v6/623.fix.html

[b3yours3lf]

I have fix my source code but I still get WA

[mido]

Anything wrong here...:

[cpp]
#include <iostream.h>

void main()
{
long n,i,count=0;
while (!cin.eof() && cin>>n && !cin.fail())
{
if (count)
cout<<endl;
count++;
int len=1;
int longI[100001];
int longI_temp[100001];
for (i=0;i<100001;i++)
{
longI=0;
longI_temp=0;
}
longI[100001-1]=1;
for (i=n;i>=1;i--)
{
int j=100001-len;
while (j<100001)
{
int factor=1;
int index=j;
while (i/factor)
{
longI_temp[index]+=longI[j]*(i%(factor*10)/factor);
longI_temp[index-1]+=longI_temp[index]/10;
longI_temp[index--]%=10;
factor*=10;
}
len = 100001-index>len ? 100001-index :len;
j++;
}
int k;
for (k=100001-len;k<100001;k++)
{
longI[k]=longI_temp[k];
longI_temp[k]=0;
}
}
cout<<n<<"!"<<endl;
for (i=100001-len;i<100001 && longI==0;i++){}
for (;i<100001;i++)
{
cout<<longI;
}
cout.flush();
}
}[/cpp]

[mido]

Got AC finally....just one more brute force check needed at the end...

[de]

why got WA@@?
I have try 0,1,2,3,4,5,6,7,8,9,10,100,150,500
but I still can't find any bug><

#include <iostream.h>

void solve(int [],int);
void out(int []);

void solve(int N[],int A)
{
int intT;
int intIF=0;
int intS=0;

for (intT=284 ;intT>=0 ;intT--)
{
N[intT]*=A;

if (intIF!=0)
intS=intIF;
else
intS=0;

if (N[intT]>=10000)
{
intIF=(N[intT]/10000);
N[intT]%=10000;
}
else
intIF=0;

N[intT]+=intS;
}
}

void out (int N[])
{
int intOK=0;
int intT;

for (intT=0 ;intT<285 ;intT++)
{
if (intOK==0 && intT==284)
cout << N[intT];
else if (intOK==0 && N[intT]==0)
continue;
else if (intOK==0 && N[intT]!=0)
{
intOK=1;
cout << N[intT];
}
else
{
if (N[intT]<10)
cout << "000" << N[intT];
else if (N[intT]<100)
cout << "00" << N[intT];
else if (N[intT]<1000)
cout << "0" << N[intT];
else
cout << N[intT];
}
}
}

int main()
{
int intN;
int intNumber[285];
int intT;

for (intT=0 ;intT<285 ;intT++)
intNumber[intT]=0;

while (cin >> intN)
{

for (intT=0 ;intT<285 ;intT++)
intNumber[intT]=0;
intNumber[284]=1;

for (intT=1 ;intT<=intN ;intT++)
solve(intNumber,intT);
cout << intN << "!" << endl;
out(intNumber);
cout << endl;
}
return 0;
}

[Red Scorpion]

Eh.....

Try how if the input is 500,
The length of output is : 1135.
I guest your array was overflow.

Code: Select all

Sample Input:
500

Sample Output:
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Good Luck

[Master]

I have solved 500! (623) at the very beginning of my registration. Now I am analyzing my accepted codes and found a very surprising thing in that code. When I give the input as the following I found a answer which is wrong

INPUT
0
1

OUTPUT
0!
2
1!
2

Here is my AC code.
[cpp]
/* @JUDGE_ID: 22453?? 623 C++ "" */
/** Submited via Valladolid ACM Online Judge Submit page v4 **/
/** IP: 203.105.153.49 **/
/** Date: 2002-09-14 10:30:19 **/

/* Function of finding factorial
* Input : int (char array)
* return : One big int (char array)
* Maximum input : Yet not defined
*/
/* For main() */ #include<stdio.h>//*/

#include<string.h>

#define MAX 5000
char *spmul(char *a1,char *a2)
{
long int l1,l2,n_d;
l1=strlen(a1);
l2=strlen(a2);
register long int i,j,k;
short int num1[MAX],num2[MAX],of=0,res[MAX];
n_d=(l1<l2)?l2:l1;
n_d++ ;
for(i=0;i<=n_d;i++)
res=0;
///////////////////////////////////////////////////
for(i=0,j=l1-1;i<l1;i++,j--)
num1=a1[j]-48;
for(i=0,j=l2-1;i<l2;j--,i++)
num2=a2[j]-48;
res[0]=0;
for(j=0;j<l2;j++)
{ for(i=0,k=j;i<l1 || of;k++,i++)
{ if(i<l1)
res[k] += num1 * num2[j] + of;
else res[k] += of;
of=res[k]/10;
res[k]=res[k]%10;
}
//////In the case of static this line are not needed////
res[++n_d]=0;
}
char a[MAX];
for(i=k-1,j=0;i>=0;i--,j++)
a[j]=res+48;
a[j]='\0';
return a;
}
char *fact(int n)
{ register int i;
char num1[2*MAX],num2[MAX];
num1[0]='2';
num1[1]='\0';
for(i=3;i<=n;i++)
{ sprintf(num2,"%d",i);
strcpy(num1,spmul(num1,num2));
}
return num1;
}
/*Sample main function*/
main(void)
{
int n;
while((scanf("%d",&n))!=EOF)
printf("%d!\n%s\n",n,fact(n));
return 0;
}

/***************************************************/
[/cpp]
I know where my code have bug but….
How 0! = 2 and 1! = 2. ???????????
How the online judge accept this.???????????

M H Rasel
CUET - Old Sailor

[Zhao Le]

I have seen lots of guys got TLE after RJ.
I wonder why and this cannot use DP.
It will surely cause OverFlow when use S[500][1135]

[Observer]

Didn't you notice that the upper limit of n has been increased to 1000 ?