## 623 - 500!

Moderator: Board moderators

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China

### 623 - 500!

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

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China
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
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### 623 & output in general

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

peter

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

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### nasty input

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
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 623-Why WA?Need more input&output sample

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
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
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
I have fix my source code but I still get WA

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 623 again

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
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Got AC finally....just one more brute force check needed at the end...

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

### 623

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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:

### 623 - Incorrect output with accepted code

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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### 623 500! TLE after ReJudged

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]
AC makes me feels good,
But WA makes me thinks hard.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Didn't you notice that the upper limit of n has been increased to 1000 ?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org