OJ Board

Posted: **Mon Aug 29, 2005 12:12 pm**

For the CE the specific error msg was sent to ur e-mail address.
U should read the mail.then u can know where is the problem of ur program.

Posted: **Sat Dec 03, 2005 7:54 pm**

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAX 5000

//declarations global
char multiple_of_divisor[10][MAX+1];
char multiples[10][MAX+1];
char factorial[1005][MAX];

//code for reversing
void rev(char *num){
	long len,i;
	char ch;
	len=strlen(num);
	for(i=0;i<len/2;i++) {
		ch=num[i];
		num[i]=num[len-1-i];
		num[len-1-i] = ch;
	}
}

//code for cutting from the stock  - used for division
void cut_stock(char *dest, char *source) {
	long len;
	long i;

	len=strlen(dest);
	dest[len]=source[0];
	dest[len+1]='\0';

	len=strlen(source);
	for(i=1;i<len;i++)
		source[i-1]=source[i];
	source[len-1]='\0';
}

//code for zero justify - i mean to add zero!
void zero_justify(char *array,long n) {
	long i;
	long len;
	len=strlen(array);
	for(i=len;i<len+n;i++)
		array[i]='0';
	array[len+n]='\0';
}

//code for removing odd zeros!
//to avoid err like 075, while it is 75 actually!
void remove_zero(char *temp) {
	int leng;
	int i;

	while(temp[0]=='0') {
			leng=strlen(temp);
			if(leng==1) break;
			for(i=1;i<leng;i++) {
				temp[i-1]=temp[i];
			}
			temp[leng-1]='\0';
	}
}


//code for compare
int compare(char *bigger, char *smaller) {
	long i;
	long x,y;

	x=strlen(bigger);
	y=strlen(smaller);

	if(x>y) return 1;
	else if(x<y) return 0;

	else {
		for(i=0;i<x;i++) {
			if(bigger[i]<smaller[i]) return 0;
			if(bigger[i]>smaller[i]) return 1;
		}
	}
return 2; //the two numbers are equal! - used in division
}


//code for addition
void addition(char *first,char *second, char *answer) {
	long x,y;
	long i;
	char backup1[MAX+1],backup2[MAX+1];
	char carry,temp_sum;

	//i dont want to destroy the data, cause i'll use them later!
	strcpy(backup1,first);
	strcpy(backup2,second);

	x=strlen(first);
	y=strlen(second);

	//to always keep first bigger - "hold_me_for_a_while" ;=)
	if(x<y) {
		auto char hold_me_for_a_while[MAX+1];
		strcpy(hold_me_for_a_while,first);
		strcpy(first,second);
		strcpy(second,hold_me_for_a_while);
		i=x;
		x=y;
		y=i;
	}

	rev(first);
	rev(second);

	zero_justify(second,x-y);

	carry=0;
	for(i=0;i<x;i++) {
		temp_sum=first[i]-'0'+second[i]-'0'+carry;
		carry=0;
		if(temp_sum>9) {
			carry=(char)(temp_sum-temp_sum%10)/10;
			temp_sum=temp_sum%10;
		}
		answer[i]=temp_sum+'0';
		temp_sum=0;
	}
	if(carry!=0) {
		answer[i]=carry+'0';
		answer[i+1]='\0';
	}
	else answer[i]='\0';

	rev(answer);
	//i kept my promise! ;-)
	strcpy(first,backup1);
	strcpy(second,backup2);

}






//code for subtraction
void subtraction(char *first, char *second, char *answer) {
	long x,y;
	long i;
	char backup1[MAX+1],backup2[MAX+1];
	char carry,temp_sub;

	//not destroying the data!
	strcpy(backup1,first);
	strcpy(backup2,second);

	x=strlen(first);
	y=strlen(second);

	//to always keep first bigger
	if(!compare(first,second)) {
		auto char hold_me_for_a_while[MAX+1];
		strcpy(hold_me_for_a_while,first);
		strcpy(first,second);
		strcpy(second,hold_me_for_a_while);
		i=x;
		x=y;
		y=i;
	}

	rev(first);
	rev(second);

	zero_justify(second,x-y);

	carry=0;
	for(i=0;i<x;i++) {
		temp_sub=first[i]-second[i]-carry;
		carry=0;
		if(temp_sub<0) {
			carry++;
			temp_sub=temp_sub+10;
		}
		answer[i]=temp_sub+'0';
		temp_sub=0;
	}
	answer[i]='\0';

	rev(answer);

	//i kept my promise again! ;-)
	strcpy(first,backup1);
	strcpy(second,backup2);

}


//code for division -"in the pounds, in the pines, where the bug can never be find... I'll shiver the whole night through!" :-)
//the bug is found! actually it was ' bugs ' :-)

void divide(char *stock, char *divisor, char *answer, char *remainder) {
	char temp[MAX+1];
	char tempo[MAX+1];
	long len;
	int i;
	long j=-1;
	int cmp_value;
	char started=0,enter;
	temp[0]='\0';
	answer[0]='\0';

	remove_zero(stock);

	//checking for zeros
	if(strcmp(stock,"0")==0) {
		strcpy(answer,"0");
		strcpy(remainder,"0");
		return;
	}

	//smaller greater
	if(compare(stock,divisor)==0) {
		strcpy(answer,"0");
		strcpy(remainder,stock);
		return;
	}

	len=strlen(stock);
	strcpy(multiple_of_divisor[0],"0");
	for(i=1;i<=9;i++) {
			addition(multiple_of_divisor[i-1],divisor,tempo);
			strcpy(multiple_of_divisor[i],tempo);
			//puts(ans);
		}


	while(len>0) {
		if(len==0) break;
		enter=1;

		while(!compare(temp,divisor)) {
			cut_stock(temp,stock);
			len--;
			remove_zero(temp);

			if(!compare(temp,divisor) && started) {
				answer[++j]='0';
				enter=0;
				break;
			}
			else if(!compare(temp,divisor)){
			cut_stock(temp,stock);
			len--;
			if(len<0) break;
			}
			remove_zero(temp);
		}
		if(len<0) break;


		for (i=1;i<=9 && enter;i++) {
			cmp_value=compare(multiple_of_divisor[i],temp);
			if(cmp_value==1){
				i--;
				break;
			}
			else if(cmp_value==2)
				break;
		}

		//a very special case
		if(i==10) i=9;

		if(enter) {
		answer[++j]=i+'0';
		started=1;
		subtraction(temp,multiple_of_divisor[i],tempo);
		strcpy(temp,tempo);
		}
		remove_zero(temp);
	}
	answer[j+1]='\0';
	strcpy(remainder,temp);
}



//code for multiplication - i used a variable name multiple_of_divisor,its actually just multiple. i didnt used a new name here... 
void multiply(char *first, char *second, char *answer) {
	int i;
	char tempo[MAX+1];
	char temp_second[MAX+1];
	char temp_ans[MAX+1];
	char another_temp[MAX+1];
	int zero_counter;
	int len;
	
	remove_zero(first);
	remove_zero(second);

	//to have some precalculated values to enhance speed for long calculations
	if(strcmp(first,"0")==0 || strcmp(second, "0")==0) {
		strcpy(answer,"0");
		return;
	}
	strcpy(temp_ans,"0");

	//to always keep first bigger
	if(!compare(first,second)) {
		auto char hold_me_for_a_while[MAX+1];
		strcpy(hold_me_for_a_while,first);
		strcpy(first,second);
		strcpy(second,hold_me_for_a_while);
	}
	
	strcpy(multiples[0],"0");
	for(i=1;i<=9;i++) {
			addition(multiples[i-1],first,tempo);
			strcpy(multiples[i],tempo);
			//puts(ans);
		}

	strcpy(temp_second,second);
	len=strlen(temp_second);
	rev(temp_second);

	zero_counter=0;
	for(i=0;i<len;i++) {
		strcpy(tempo,multiples[temp_second[i]-'0']);
		if(i) zero_justify(tempo,++zero_counter);
		remove_zero(tempo);
		addition(tempo,temp_ans,another_temp);
		strcpy(temp_ans, another_temp);
	}
strcpy(answer,temp_ans);
}







//main function

void main() {
	char one[]="1";
	char next_num[8]="1";
	char ans[MAX+1];
	int i;
	strcpy(factorial[1],"1");
	for(i=2;i<=1000;i++) {
		addition(next_num,one,ans);
		strcpy(next_num,ans);
		multiply(factorial[i-1],next_num,ans);
		strcpy(factorial[i],ans);
	}

	while(scanf("%d",&i)==1) {
		printf("%d!\n",i);
		printf("%s\n",factorial[i]);
	}

}

please tell me, why the RUNTIME ERROR loves me so much???

Posted: **Sat Dec 03, 2005 9:02 pm**

The problem is probably in

Code: Select all

void zero_justify(char *array,long n) { 
   long i; 
   long len; 
   len=strlen(array); 
   for(i=len;i<len+n;i++) 
      array[i]='0'; 
   array[len+n]='\0'; 
}

len+n may exceed array size.

Posted: **Sat Dec 03, 2005 9:42 pm**

thanx for your reply,
but how can you say that, i have taken MAX as 5000.
and this didnt bothered when i solved other biging probs!
[/quote]

Posted: **Sat Dec 03, 2005 10:12 pm**

Well, it runs smoothly in my compiler too. But you might be interested, the outputs are wrong! And one more thing, you forgot about 0!

Posted: **Sun Dec 04, 2005 3:12 am**

Oh my god! Thanks a lot for informing so.
I solved Krakovia of volume 109. And got AC with the same code. So i can suppose there is nothing wrong with the bigint part.
I checked for 0!, and you know what, i still got RE.
If the outputs are wrong, it may should show WA. And why is it showing RE?

Thanks a lot for your kind helping.

Posted: **Thu Dec 29, 2005 8:40 am**

I wrote problem as follow:
#include <deque>
#include <vector>
#include <string>
#include <iostream>
using namespace std;

class StringMath
{
public:
deque<int> mult(deque<int> input, int num);
string solve(int n);
int simplesolve(int n);
string toString4(int num);
string toString(int num);
};

int StringMath::simplesolve(int n)
{
int ret = 1.0;
int i;
for(i=1;i<n;i++) ret = ret * i;
return ret;
}

string StringMath::solve(int n)
{
if(n<=10){
return toString(simplesolve(n));
}
deque<int> number;
number.push_back(2);
int i;
for(i=3;i<=n;i++){
number = mult(number,i);
}
string ret;
ret = toString(number[0]);
for(i=1;i<number.size();i++){
ret = ret + toString4(number);
}
return ret;
}

string StringMath::toString(int num)
{
int a = num;
int b;
string ret;
while(true)
{
b = a%10;
a = (int)(a/10);
ret.insert((string::size_type)0,1,char(b+'0'));
if(a==0) break;
}
return ret;
}

string StringMath::toString4(int num)
{
int a = num;
int b;
string ret;
int k = 0;
while(k<4)
{
b = a%10;
a = (int)(a/10);
ret.insert((string::size_type)0,1,char(b+'0'));
k++;
}
return ret;
}

deque<int> StringMath::mult(deque<int> input, int num)
{
deque<int> ret;
int i;
int a,b,c;
a = 0;
b = 0;
c = 0;
for(i=input.size()-1;i>=0;i--)
{
a = input;
a = a*num+c;
b = a%10000;
c = int(a/10000);
ret.push_front(b);
//cout<<a<<" "<<b<<" "<<c<<endl;
}
if(c!=0) ret.push_front(c);
return ret;
}

int main()
{
StringMath SM;
int n;
string ret;
while(true)
{
cin>>n;
ret = SM.solve(n);
cout<<n<<"!"<<endl;
cout<<ret<<endl;
}
}

In my computer, I can calculate 1000! very quickly(less than 1 second), but after I submit,
the system tell me I exceed time limit.

Posted: **Thu Dec 29, 2005 9:23 am**

Use memoization, ie. precalculate the values from 0! to 1000! and save in an array. Just retrieve from it on input.
While calculating don't forget to use the formula

Code: Select all

n! = n * (n-1)!

Posted: **Thu Dec 29, 2005 2:31 pm**

If I precalculate the value, I can I store them in array,
1000! have more than 1000 digits, I can not write them down,
and then store them i a array

Posted: **Thu Dec 29, 2005 5:32 pm**

Instead of a single string, you will have to use an array of Strings to store the results.

Posted: **Fri Dec 30, 2005 9:37 am**

I can not catch you answer very well.
can someone give me a more clearly answer,
If some one can tell me how to modify my code , It will be very helpful

Posted: **Fri Dec 30, 2005 10:41 am**

OK!
Declare an array of strings to hold factorial values

Code: Select all

string factorial[1001];

Since you know 0! is 1, therefore

Code: Select all

factorial[0]=1;

Then use the previously posted formula to find the factorials

Code: Select all

for(int i=1;i<1001;i++)
   factorial[i]=i*factorial[i-1];

Do your string calculation the way you have done.
Now enter the loop for taking input and showing output. When you are asked to show factorial of n just show

Code: Select all

cout<<factorial[n];

Hope these help.

Posted: **Mon Jan 16, 2006 8:52 pm**

I don't know what's wrong with my code. I kept getting RE. It work perfectly in my compiler except that the maximum size can not exceed 200 in my compiler (maybe because of memory limit). Someone please help me.

___________________________________________________
code removed
___________________________________________________

Posted: **Mon Jan 16, 2006 10:41 pm**

Declare

Code: Select all

bignum num[maxSize]; 
bignum timer[maxSize];

as staitc or global.

Posted: **Sat Jan 21, 2006 5:17 pm**

thx man. I got AC. I wonder why as a global or static make any difference.

OJ Board

623 - 500!

623 - 500! - why do i get RE!!

623 500! Why exceed time limit

Thank your, But

sorry

623 why RE