## 623 - 500!

Moderator: Board moderators

### 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[i]) + tmp;
c->l[i] = cur % MODULE_NUM;
tmp = cur / MODULE_NUM;
}

i = a->size; /* Can be omitted? */
while (tmp > 0)
{
c->l[i] = 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[i - 1]);
}

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

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

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[i] == 0)) i--;
if (i == 0)
{
init_big(a);
set_big_u(a, 1);
}
else
copy_big(a, g_save_num[i]);

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;
}
idler
New poster

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

### 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]
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

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.
arc16
Learning poster

Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

### 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.... :(
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### 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[i]=0;
arr[i]=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[i]==0) i++;
printf("%d!\n",fak);
j=1;
for(;i<1135;i++)
{
printf("%d",arr[i]);
if(j%80==0) printf("\n");
j++;
}
printf("\n");
}
}
}
[/c]
b3yours3lf
New poster

Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

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
ec3_limz
Learning poster

Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

I have fix my source code but I still get WA
b3yours3lf
New poster

Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 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[i]=0;
longI_temp[i]=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[i]==0;i++){}
for (;i<100001;i++)
{
cout<<longI[i];
}
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...
mido
Learning poster

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

### 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;
}
de
New poster

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

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:500Sample Output:1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000`

Good Luck
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 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[i]=0;
///////////////////////////////////////////////////
for(i=0,j=l1-1;i<l1;i++,j--)
num1[i]=a1[j]-48;
for(i=0,j=l2-1;i<l2;j--,i++)
num2[i]=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[i] * 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[i]+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
Master
Learning poster

Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm

### 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.
Zhao Le
Learning poster

Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

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
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Next

### Who is online

Users browsing this forum: No registered users and 1 guest