623 - 500!

[Ghust_omega]

Hi !! SePulTribe nice to know that you get AC !! and I thinking in put the input from 0...1000 in somewhere and the ouput,of course,
Keep posting !!

[SePulTribe]

Haha I will keep posting. And thanks!

[roticv]

Any idea why I keep getting RE?

Code seem to work fine for me

Code: Select all

#include <stdio.h>
#include <string.h>

char str1[1000];
char str2[4000];
char final[4000];
char cal[1500][4000];
int i, j, ii, len1, len2, tmp, limit, result, N;


int main(){
	final[0] = 1;
	cal[0][0] = 1;
	len2 = 1;
	for (ii=1;ii<=1000;ii++){
		len1 = sprintf(str1,"%d",ii);
		for (i=0;i<len2;i++){
			str2[i] = final[i];
		}
		for (i=0;i<(len1+1)/2;i++){
			tmp = str1[i] - '0';
			str1[i] = str1[len1-i-1] - '0';
			str1[len1-i-1] = tmp;
		}
		for (i=0;i<len1;i++){
			for (j=0;j<len2;j++){
				tmp = str2[j] * str1[i];
				final[i+j] += tmp;
				final[i+j+1] += final[i+j]/10;
				final[i+j] = final[i+j] % 10;
			}
		}
		for (i=4000;final[i]==0;i--){
			if (i==0){
				break;
			}
		}
		len2 = i+1;
		for (i=0;i<len2;i++){
			cal[ii][i] = final[i];
		}
	}
	while (scanf("%d",&N)!=EOF){
		printf("%d!\n",N);
		for (i=4000;cal[N][i]==0;i--){
			if (i==0){
				break;
			}
		}
		for (;i>=0;i--){
			printf("%c",cal[N][i]+'0');
		}
		printf("\n");
	}
	return 0;
}

[gits]

Code: Select all

char final[4000];
...
for (i=4000;final[i]==0;i--){ 

final will be final[4000] in the first iteration, which may be the cause of RE. Either make i=3999 or increase final[] size to 4001.

Same thing here:

Code: Select all

for (i=4000;cal[N][i]==0;i--){ 

When you declare something like, "int array[100];" the valid positions are array[0] through array[99], for a total of 100 positions, but array[100] is invalid.

[roticv]

Thanks for you help. Managed to solve another few more questions because of your help - pointing out the mistake of mine.

[sunnycare]

first ,code here:it's compiled error

Code: Select all

#include <cstdio>
using namespace std;
#define BASE 1000000000
#define MAXNUM 999999999
struct bignum
{
	long val[300];                   
	long len;
};
bignum tab[1001];
void mul(bignum &a,long b,bignum &r)
{
	long long tmp;
	long i;
	long carry=0;
	for(i=0;i<a.len;i++)
	{
                    
		tmp=long long(a.val[i])*b+carry;
		r.val[i]=tmp%BASE;
		carry=tmp/BASE;
	}
	if(carry!=0)
	{
		r.val[i++]=carry;
	}
	r.len=i;

}
void printNum(bignum &n)
{
	long i=n.len-1;
	printf("%d",n.val[i]);
	for(--i;i>=0;i--)
		printf("%09d",n.val[i]);
}
void main()
{
	
	tab[0].val[0]=1;
	tab[0].len=1;
	long i;
	for(i=1;i<=1000;i++)
		mul(tab[i-1],i,tab[i]);
	long n;
	while(scanf("%d",&n)==1)
	{
		printf("%d!\n",n);
		printNum(tab[n]);
		printf("\n");
	}
}

but if i change the code in struct node
long val[300] =====> long long val[300]
and the code in mul function
tmp=long long(a.val)*b+carry;===>tmp=(a.val)*b+carry;

my code accepted... why?

(both code is compiled right in vc.net & winxp)


by the way is there a free gcc compiler for winxp......

[sunnycare]

who can help me?

[..]

tmp=long long(a.val)*b+carry;

Wrong syntax, the correct should be

tmp=(long long)(a.val)*b+carry;

Don't argue why VC can compile, the judge is using gcc/g++

[sunnycare]

sorry..

where to download gcc for windows??

someone tell me go to cygwin.com

but i dont know what to download??

it seems no gcc?

[..]

Cygwin is a bit complicate for beginner....You can try DevC++, just google it and you will find it.

[[_TANG_]]

Hi, I've solved this problem, here in my PC works fine I test it on LINUX (Red hat 9) and on Borland C++ compiler even UNIX ( at my job ... ) and it's OK, but when I send my code to be judged always return the message "Runtime Error (SIGSEGV)" invalid memory reference ... I don't know why it runs perfectly, I know my multiplication function its OK 'cause with the same code I solved the problem 10106 (Product) and I check my results with a calculator and are OK ... can anyone help me?

Can anyone have the result of 500! ?

Here's part of my code I think the problem is in these lines

Code: Select all

#define MAX 3000
#define MAX_FACT 500
#define MAX_LEN 1140

void main()
{
	char num1[MAX], num2[MAX], res[MAX];
	char resultados[MAX_FACT][MAX_LEN];
	int len1, len2, n, c;
	
	/* Precalcalculate factorials to avoid TLE */
	strcpy(resultados[0],"1");
	
	for(c = 1; c < 500; c++)
	{
		sprintf(num1,"%d",c+1);
		strcpy(num2,resultados[c-1]);
		
		len1 = strlen(num1);
		len2 = strlen(num2);
		
		if(len1 < len2)
			multiplicacion(num1,num2,res);
		else
			multiplicacion(num2,num1,res);
		
		strcpy(resultados[c],res);
	}
	
	while(cin >> n)
		cout << n << "!\n" << resultados[n-1] << endl;
}

thnx a lot!!

________________
[_TANG_]

[sumankar]

Read the problem description well, the html version, where the latest is, usually, if they make changes that is to the problem description.Here is what I believe will help you:

Assumptions: Value of a number ``n" which factorial should be calculated of does not exceed 1000 (although 500! is the name of the problem, 500! is a small limit).

from the problem description at http://online-judge.uva.es/p/v6/623.html.

Change the macros, read the old posts to find out how many digits 1000! has, etc and see.

HTH,
Suman.

[[_TANG_]]

Thnx sumankar, I've already change my precalculation to 1000! using DP, but I'm still having the same error.

I've another question ... is there NEGATIVE factorials?, maybe my mistake is something like that

Do you have some critical I/O?
_____________
[_TANG_]

[[_TANG_]]

Thnx a lot sumankar.

I reviewed all my code, my mistake was that I forgot 0! and that was my error I was looking for resultados[-1], now I've got AC ...

A silly mistake


___________________
[_TANG_]

[unuguntsai]

I don't know why RE??

Code: Select all

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

#define LEN 2600
#define MAX 1001

int main()
{
      int num[MAX][LEN] , n , i ;

      for( i = 0 ; i < MAX ; i++)
        for( int j = 0 ; j < LEN ; j++ )
          num[i][j] = 0 ;

      num[0][0] = 1 ;
      num[1][0] = 1 ;

      for( i = 2 ; i < MAX ; i++ )
      {
        for( int j = 0 ; j < LEN - 1 ; j++ )
        {
          num[i][j] += num[i-1][j] * i ;
          num[i][j+1] += num[i][j] / 10 ;
          num[i][j] %= 10 ;
        }
      }

      while( scanf("%d" , &n ) != EOF && n >= 0 )
      {
        printf("%d!\n" , n ) ;
        for( i = LEN - 1 ; i >= 0 ; i-- )
          if( num[n][i] != 0 )  break ;
        for( ; i >= 0 ; i-- )
          printf("%d" , num[n][i] ) ;
        printf("\n") ;
      }
      return 0;
}

Please Help Me~