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
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Post by SePulTribe »

Haha I will keep posting. And thanks!

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

623 RE

Post by 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
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

Post by 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
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv »

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

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

623 Compiled error!

Post by 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
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare »

who can help me?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

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++
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by 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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Cygwin is a bit complicate for beginner....You can try DevC++, just google it and you will find it.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

[_TANG_]
New poster
Posts: 15
Joined: Wed May 04, 2005 12:28 am
Location: Mexico

623 -> 500! Plz help ... ='(

Post by [_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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by 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_]
New poster
Posts: 15
Joined: Wed May 04, 2005 12:28 am
Location: Mexico

Post by [_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_]
New poster
Posts: 15
Joined: Wed May 04, 2005 12:28 am
Location: Mexico

Nevermind

Post by [_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 ... :lol:

A silly mistake :oops:


___________________
[_TANG_]

unuguntsai
New poster
Posts: 6
Joined: Mon Aug 15, 2005 4:40 am

623 Why RE??

Post by 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~

Post Reply

Return to “Volume 6 (600-699)”