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

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

623 - 500!

Post by idler » Fri Feb 22, 2002 6:27 am

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

Post by idler » Fri Feb 22, 2002 6:27 am

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

Post by zsepi » Thu Sep 26, 2002 7:49 pm

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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Fri Sep 27, 2002 1:17 am

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

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

nasty input

Post by zsepi » Fri Sep 27, 2002 1:43 am

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

Post by b3yours3lf » Thu Jan 09, 2003 2:53 am

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

Post by ec3_limz » Sun Jan 12, 2003 5:27 pm

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

Post by b3yours3lf » Wed Jan 15, 2003 4:35 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

Post by mido » Mon Feb 17, 2003 11:55 am

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

Post by mido » Sat Feb 22, 2003 5:43 pm

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

Post by de » Sat Mar 08, 2003 3:50 pm

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

Post by Red Scorpion » Wed Mar 12, 2003 5:06 am

Eh..... :lol: :lol: :lol:

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 :lol: :lol: :lol:

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

623 - Incorrect output with accepted code

Post by Master » Wed Aug 13, 2003 6:33 am

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

Post by Zhao Le » Sun Jan 18, 2004 9:27 am

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

Post by Observer » Sun Jan 18, 2004 11:27 am

Didn't you notice that the upper limit of n has been increased to 1000 :D ?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 6 (600-699)”