OJ Board

Code: Select all

program uva495;
const
	dlen = 1100;
var
	f : array [0..5100,1..dlen] of byte;
	s : array [0..5100] of word;
	i, a, max : integer;

procedure SumLong (a, b, c : integer);
var
	m, i : integer;	
begin
	m := s[b];
	for i := dlen downto m do
	begin
		f[c,i] := f[c,i] + f[a,i] + f[b,i];
		f[c,i-1] := f[c,i] div 10;
		f[c,i] := f[c,i] mod 10;		
	end;
	if (f[c,m-1] > 0) then s[c] := m-1 else s[c] := m;
end;

begin
	fillchar(f,sizeof(f),0);
	f[0,dlen] := 0;
	f[1,dlen] := 1;
	f[2,dlen] := 1;
	s[0] := dlen;
	s[1] := dlen;
	s[2] := dlen;
	max := 2;
	while not eof(input) do
	begin
		readln (a);
		if (a > max) then
		begin
			for i := max + 1 to a do
				SumLong (i-2,i-1,i);
			max := a;
		end;
		write ('The Fibonacci number for ',a,' is ');
		for i := s[a] to dlen do write (f[a,i]);
		writeln;
	end;
end.

Code: Select all

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

#define MAX	1050

void str_sum(char *min, char *max, char **ret);
char *strrev(char *str);

void main(void)
{
	char a[MAX], b[MAX], v[MAX];
	char *p[4];
	int c;

	while ( scanf("%d", &c) != -1 ) 
	{
		printf("The Fibonacci number for %d is ", c);

		if ( c == 0 ) 
			strcpy(v, "0");
		else if ( c == 1 ) 
			strcpy(v, "1");
		else
		{
			strcpy(a, "0");
			strcpy(b, "1");

			c -= 1;

			p[0] = a;
			p[1] = b;
			p[2] = v;

			while ( 1 ) 
			{
				str_sum(p[0], p[1], &p[2]);			// v = a+b;
				c--;

				if ( c == 0 ) break;

				p[3] = p[0];

				p[0] = p[1];						// a = b;
				p[1] = p[2];						// b = v;
				p[2] = p[3];
			}
		}

		printf("%s\n", strrev(p[2]));
	}
}

void str_sum(char *min, char *max, char **ret)
{
	int i;
	int max_len = strlen(max);
	int min_len = strlen(min);
	int carry;

	carry = 0;

	for ( i = 0 ; i < min_len ; i++ ) 
	{
		(*ret)[i] = min[i] + max[i] - '0' + carry;

		if ( (*ret)[i] > '9' ) 
		{
			carry = 1;
			(*ret)[i] -= 10;
		}
		else
			carry = 0;
	}

	if ( min_len ^ max_len ) 
		carry += max[i] - '0';

	if ( carry ) 
	{
		(*ret)[i] = '0' + carry;
		(*ret)[i+1] = 0;
	}
	else
		(*ret)[i] = 0;
}

char *strrev(char *str)
{
	int len = strlen(str);
	int i;
	char ch;

	for ( i = 0 ; i < len / 2 ; i++ ) 
	{
		ch = str[i];
		str[i] = str[len-i-1];
		str[len-i-1] = ch;
	}

	return str;
}

Code: Select all

#include <iostream.h>

void main()
{
   int n,a[1050],b[1050],c[1050],i,s,t;
   while (cin>>n)
   {
      for (i=1;i<1050;i++) { a[i]=0; b[i]=0; }
      a[0]=1;a[1]=1;
      b[0]=1;b[1]=1;
      c[0]=1;c[1]=1;
      if (n==0) c[1]=0;
      for (t=3;t<=n;t++)
      {
	 s=0;
	 c[0]=b[0];
	 for (i=1;i<=c[0];i++)
	 {
	   c[i]=(a[i]+b[i]+s)%10;
	   s=(a[i]+b[i]+s)/10;
	 }
	 if (s>0) {c[0]++;c[c[0]]=s;}
	 for (i=0;i<=b[0];i++) a[i]=b[i];
	 for (i=0;i<=c[0];i++) b[i]=c[i];
      }
      cout<<"The Fibonacci number for "<<n<<" is ";
      for (i=c[0];i>0;i--) cout<<c[i];
      cout<<endl;
   }
}

Code: Select all

#include <iostream.h>

void main()
{
   const int max=5001;
   int n,a[max][1050],i,t;
   for (i=0;i<1050;i++) for (t=0;t<max;t++) a[t][i]=0;
   a[0][0]=1;a[0][1]=0;
   a[1][0]=1;a[1][1]=1;
   a[2][0]=1;a[2][1]=1;
   for (t=3;t<max;t++)
   {
      int s=0;
      a[t][0]=a[t-1][0];
      for (i=1;i<=a[t][0];i++)
      {
	a[t][i]=(a[t-1][i]+a[t-2][i]+s)%10;
	s=(a[t-1][i]+a[t-2][i]+s)/10;
      }
      if (s>0) {a[t][0]++;a[t][a[t][0]]=s;}
   }
   while (cin>>n)
   {
      cout<<"The Fibonacci number for "<<n<<" is ";
      for (i=a[n][0];i>0;i--) cout<<a[n][i];
      cout<<endl;
   }
}

Code: Select all

/*
495 fibonacci freezes
submission 1 TLE 2 WA 3 RE
coded at 3:26 am on 13th oct

after the tle i changed the code, used memory
i hate runtime error!!
*/


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

 


//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 zero justify
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 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);

}


void main() {
	int num,i;
	char sum[5001][MAX+1];
	
	strcpy(sum[0],"0");
	strcpy(sum[1],"1");
	strcpy(sum[2],"1");
	for(i=3;i<=5000;i++) {
			addition(sum[i-1],sum[i-2],sum[i]);
			}
	 while(scanf("%d",&num)==1) {
                printf("The Fibonacci number for %d is %s\n",num,sum[num]);

	}

	
}

Code: Select all

void main() { 
   int num,i; 
   char sum[5001][MAX+1]; 
    
   strcpy(sum[0],"0");