10183 - How Many Fibs?

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Sep 24, 2004 4:46 pm

Hi!!! Eduard how about this
Input:

Code: Select all

83 346930886
77 214636915
93 424238335
86 149760492
49 189641421
62 350490027
90 102520059
63 467513926
40 40383426
72 303455736
11 21595368
67 226956429
82 361021530
62 233665123
67 468703135
29 301979802
22 135723058
69 125898167
93 89018456
11 156478042
29 153377373
21 414544919
84 256898537
98 473594324
15 38664370
13 184803526
91 424268980
56 249241873
62 42999170
96 135497281
5 84420925
84 327336327
36 159126505
46 132621729
13 433925857
24 84353895
82 1100545
14 48233367
34 85990364
43 260313750
1 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0 0
ouput:

Code: Select all

32
31
31
30
32
32
29
33
29
32
30
31
32
31
33
34
32
30
28
34
32
35
31
32
30
35
31
31
28
29
35
32
31
31
37
31
20
31
31
32
474
Hope its Helps
Keep posting!!! :D

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sat Sep 25, 2004 2:22 pm

Ghust_omega My program gives right answers to all of your tests.I think tere is just one good input that I can't find and that why got WA.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

ica28
New poster
Posts: 1
Joined: Sat May 14, 2005 12:20 am

10183 How many Fibs.. Compile Error

Post by ica28 » Sat May 14, 2005 12:41 am

this source is Compile Error on online judge
but this source run on my computer
Why Compile Error??

Code: Select all

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std ;

const int MAX = 101 ;
const int FIBMAX = 45 ;
const int STRFIBMAX = 407 ;
void Init( int* , string* ) ;
int GetCnt( string , string* ) ;
bool Fibs( string , string* ) ;

int main( void )
{
	string Num[2] ;
	string strFibs[STRFIBMAX] ;
	int nFibs[FIBMAX] ;

	Init( nFibs , strFibs ) ;

	while( 1 )
	{
		cin >> Num[0] ;
		cin >> Num[1] ;
		if ( ( Num[0] == "0" ) && ( Num[1] == "0" ) )
			break ;
		cout << GetCnt( Num[1] , strFibs ) - GetCnt( Num[0] , strFibs ) 
			+ ( Fibs( Num[0] , strFibs ) ? 1 : 0 ) << endl ;
		
	}
	return 0 ;
}

int GetCnt( string num , string* strFib )
{
	int cnt = 0 ;
	int i ; 
	for ( i = 0 ; i < STRFIBMAX ; i++ )
	{
		if( num.length() > strFib[i].length() )
		{
			cnt++ ;
		}
		else if( num.length() == strFib[i].length() )
		{
			if ( num >= strFib[i] )
				cnt++ ;
		}
	}
	return cnt ;
}
bool Fibs( string num , string* strFib )
{
	int i ;
	for ( i = 0 ; i < STRFIBMAX && strFib[i].length() <= num.length() ; i++ )
	{
		if ( num == strFib[i] )
			return true ;
	}
	return false ;
}

void Init( int* nFib , string* strFib)
{
	int i = 2 , j ;
	int carry = 0 ;
	nFib[0] = 1 ;
	nFib[1] = 2 ;
	int len1, len2 ;
	char*  temp , *tp1 , *tp2 ;
	char chtp[10] ;
	int tpi ;

	while( 1 )
	{
		nFib[i] = nFib[i-1] + nFib[i-2] ;
		
		if ( nFib[i] < nFib[i-1] )
			break ;
		i++ ;
	}
	for ( i = 0 ; i < FIBMAX ; i++ )
	{
		itoa( nFib[i] , chtp , 10 ) ;		
		strFib[i] = chtp ;
	}

	i = FIBMAX ;
	
	while ( strFib[i-1].length() < 101 )
	{
		len1 = strFib[i-1].length() ;
		len2 = strFib[i-2].length() ;
		temp = new char[ len1 + 1 ] ;
		tp1 = new char[ len1 + 1 ] ;
		tp2 = new char[ len2 + 1 ] ;
		strcpy( tp1 , strFib[i-1].c_str() ) ;
		strcpy( tp2 , strFib[i-2].c_str() ) ;
		temp[len1] = '\0' ;
		for ( j = 0 ; j < len2 ; j++ )
		{
			tpi = tp1[ len1 - j - 1 ] - '0' + 
			      tp2[ len2 - j - 1 ] - '0' + carry ;
			
			if ( tpi >= 10 )
			{
				carry = 1 ;
				tpi -= 10 ;
			}
			else 
				carry = 0 ;
			temp[len1 - j - 1 ] = tpi + '0' ;
		}
		if ( len1 > len2 )
		{
			tpi = tp1[0] - '0' + carry ;
			if ( tpi > 9 )
			{
				carry = 1 ;
				tpi -= 10 ;
			}
			temp[0] =  tpi + '0' ;
		}
		if ( carry )
		{
			strFib[i] = '1' ;
			strFib[i] = strFib[i] + temp ;
			i++ ;
		}

		else
			strFib[i++] = temp ;

		delete [] temp ;
		delete [] tp1 ; 
		delete [] tp2 ;
	}
}

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Sat May 14, 2005 9:57 am

85: implicit declaration of function `int itoa(...)'

The function itoa is (perhaps surprisingly) not a standard C++ function.

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

Fibonacci, ....

Post by rmotome » Fri Jul 15, 2005 2:01 pm

There is an error in problem 10183 (How many Fibs?) ..... F[2] is defined as 2 instead of 1; you must however use the information as given in order to get an AC.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: Fibonacci, ....

Post by Martin Macko » Fri Jul 29, 2005 8:36 am

well, it depends... everybody defines it in his own way :)

anyway, problem specific posts would better fit to "Help on the Problemset" forums. (eg. http://online-judge.uva.es/board/viewforum.php?f=9)

vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:

Algorithm

Post by vijay03 » Sat Dec 30, 2006 10:32 pm

Whats the algorithm for this problem?

1.Using strings, gen upto 5000th fib.

2.Then from a to b, compare each no inbetween with fib ns to see how many fib nos are there in the range.

Wont this produce TLE? Since potentially we can compare 1 to 1^100 with 5000 fib nos?

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Sat Dec 30, 2006 11:02 pm

Use something like lower_bound and upper_bound :) u must search it binary.

vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:

Post by vijay03 » Mon Jan 01, 2007 9:23 am

Can`t binary be used only for searching an exact term? If we use lower_bound and upper_bound, we`ll have to find the smallest fib greater than lower_bound and the highest fib lower than upper_bound and subtract the indices of those two fibs to get the answer right? So how can we use binary search for that?

mad
New poster
Posts: 3
Joined: Sun Jun 24, 2007 11:51 pm

Post by mad » Wed Jul 04, 2007 6:25 am

I'm not managing to count the fibonacci numbers in a write way. Can someone help me? I'm having large answers (much more than the right one).
Thank you in advance!

Code: Select all

#include <stdio.h> 
#include <string.h> 
#define MAXDIGITS 101 

typedef struct 
{ 
  char digits[MAXDIGITS]; 
  int signbit; 
  int lastdigit; 
} Bigint; 

char * 
sumbigint (char [], char []); 

main () 
{ 
    int quantfib; //quantity of fibonacci numbers in the interval 
    int num1; 
    int num2; 
    Bigint naux1; 
    Bigint naux2; 
    int i; 
    int j; 
    Bigint fibo[5000]; 
    
    scanf ("%s %s\n", &naux1.digits, &naux2.digits); 
    while (strcmp (naux1.digits, "0") || strcmp (naux2.digits, "0")) 
      {  
        quantfib = 0; 

        strcpy (fibo[0].digits, "1"); 
        strcpy (fibo[1].digits, "2"); 
        
        //completing the array of fibonacci numbers 
        for (i = 2; i < 5000; i++)      
          strcpy (fibo[i].digits, sumbigint (fibo[i - 1].digits, fibo[i - 2].digits)); 

        //counting the numbers of fibonacci numbers in the interval 
        for (i = 0; i < 5000; i++)      
          { 
            if ((strlen (fibo[i].digits) > strlen (naux1.digits)) && (strlen (fibo[i].digits) < strlen (naux2.digits))) 
              quantfib++; 

            else if ((strlen (fibo[i].digits) == strlen (naux1.digits)) && (strlen (fibo[i].digits) == strlen (naux2.digits))) 
              if ((strcmp (fibo[i].digits, naux1.digits) >= 0) && (strcmp (fibo[i].digits, naux2.digits) <= 0)) 
                quantfib++; 

            else if ((strlen (fibo[i].digits) == strlen (naux1.digits)) && (strlen (fibo[i].digits) < strlen (naux2.digits))) 
              if (strcmp (fibo[i].digits, naux1.digits) >= 0) 
                quantfib++; 
            
            else if ((strlen (fibo[i].digits) > strlen (naux1.digits)) && (strlen (fibo[i].digits) == strlen (naux2.digits))) 
              if (strcmp (fibo[i].digits, naux2.digits) <= 0) 
                quantfib++; 
          }          
        
        printf ("%d\n", quantfib); 
        scanf ("%s %s\n", &naux1.digits, &naux2.digits);      
      } 
} 

char * 
sumbigint (char str1[], char str2[]) 
{ 
  int i; //always associated with str1 
  int j; //always associated with str2 
  int psum; //indicates the current position of the sum of the bigints 
  int carry; 
  char *sum;//result of the sum 
  int vsum;//value of a temporary sum 
  int tammaj;//the size of the biggest number 
  int temp; 
  int tmin;//the size of the lowest number 
  
  if (strlen(str1) >= strlen(str2)) 
    { 
      tammaj = strlen(str1); 
      tmin = strlen(str2); 

      i = tammaj - 1; 
      j = tmin - 1; 
    } 
  else 
    { 
      tammaj = strlen(str2); 
      tmin = strlen(str1); 
  
      i = tmin - 1; 
      j = tammaj - 1; 
    } 
  
  carry = 0; 
  //more two characters (one for '\0' and another for one possible carry 
  sum = malloc (sizeof (char) * (tammaj + 2)); 
  psum = 0; 
  
  do 
    { 
      //making the sum from right to left 
     vsum = (str1[i] - '0') + (str2[j] - '0') + carry; 
     if (vsum > 9) 
       carry = 1; 
     else 
       carry = 0; 
        
      sum[psum] = (vsum % 10) + '0'; 
      i--; 
      j--; 
      psum++; 
    } while ((i >= 0) && (j >= 0)); 
    
   //completing the sum of bigints 
          
   if (strlen (str1) == tammaj) 
       while (psum < tammaj) 
        {  
          if (vsum > 9) 
            {  
              vsum = carry + (str1[i] - '0'); 
              sum[psum] = (vsum % 10) + '0'; 
              i--; 
              psum++; 
            } 
          else 
            { 
              sum[psum] = str1[i]; 
              psum++; 
            } 
        }        
     else 
       while (psum < tammaj) 
        {  
          if (vsum > 9) 
            {  
              vsum = carry + (str2[j] - '0'); 
              sum[psum] = (vsum % 10) + '0'; 
              j--; 
              psum++; 
            } 
          else 
            { 
              sum[psum] = str2[j]; 
              psum++; 
            } 
        }          
  
  if (vsum > 9) 
    { 
      sum[psum] = '1'; 
      psum++; 
      tammaj++; 
    } 

   //reversing the result (the sum) 
   for (i = 0, j = tammaj - 1; i < j; i++, j--) 
     { 
       temp = sum[i]; 
       sum[i] = sum[j]; 
       sum[j] = temp; 
     }  
  
  sum[psum] = '\0'; 
  return sum; 
}


armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

How to debug the program to find the reason of RE

Post by armansuleimenov » Tue Sep 25, 2007 3:20 am

I'm using BigInteger class (http://online-judge.uva.es/board/viewto ... shed+suman).
I've run my program with all the tests from the board, it solves all the tests correctly. But I'm getting Runtime Error from judge. What is the reason of RE? How to debug my program to find the reason (debugging using OJ will help me with other problems too:))?
Here is my code:

Code: Select all

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <strstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

using namespace std;

namespace BigMath
{
  ............... see the link above
}

using namespace BigMath;

int main ()
{
  //ifstream fin("p.in");
  BigInteger fibo[510];
  DATATYPE i;
  i=1;
  BigInteger& a=*new BigInteger(i);
  BigInteger& b=*new BigInteger(i);
  BigInteger& c=*new BigInteger(i);
  fibo[2]=b;
  for(i=3;i<=500;++i)
    {
      c=a+b;
      a=b;
      b=c;
      fibo[i]=b;
    }
  cin >> a >> b;
  while(!(a.isZero()&&b.isZero()))
  {
    int cnt=0;
    for(i=2;i<=500;++i)
    {
      if(fibo[i]>=a && fibo[i]<=b)
	 cnt++;
      if(fibo[i]>b)break;
    }
    cout<<cnt<<endl;
    cin >> a >> b;
  }
  return 0;
}

User avatar
mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

Post by mrunmoy » Fri Dec 28, 2007 11:41 pm

Hi,

I have run through all the available test cases posted here related to problem number <10183> still i get WA.
6140898 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 20:37:44
6140883 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 20:25:29
6140876 How Many Fibs? Wrong answer C++ 0.020 2007-12-28 20:12:23
6140869 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 20:03:10
6140846 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 19:43:36
6140823 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 19:27:58
6140793 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 19:13:37
6140778 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 19:06:44
6140023 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 11:10:19
6139972 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 09:50:49
6139651 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 06:52:29
can anyone suggest some more test cases plz?

Here goes my code:-

Code: Select all

/* @JUDGE_ID: 59960OQ 10183 C "Brute Force" */

/* Solution to ACM UVa Problem 10183 - How many Fibs? */
/* Author- Mrunmoy Samal*/

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

#define EQ 0
#define GT 1
#define LT -1

#define MAX_SIZE 484
#define MAX_COL 102
char result[MAX_COL];
char sum[MAX_COL];
char prev[MAX_COL];
struct struct_tag
{
    char LookUp[MAX_SIZE][MAX_COL];
}LookUpTable;

char a_fib[MAX_COL] =
"1000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000";
char b_fib[MAX_COL] =
"1000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000";

int firsttime = 1;

int add(void);
int compareBigInteger(int k,char ch);

int main()
{
    int fib; //  0 <= n <= 5000
    int i,j,count,eqA,eqB,done,found;
    char *ptrSrc,*ptrTgt,*ptrTgt2;
    /*clock_t start = clock();*/
    fib = 483;
    result[0] = '1';
    result[1] = '\0';

    for(i=0;i<=fib;i++)
    {
        add(); // sum = result + prev
        ptrSrc = result;ptrTgt = prev;
        while(*ptrTgt++=*ptrSrc++); // prev = result
        ptrSrc = sum;ptrTgt = result;
        ptrTgt2 = LookUpTable.LookUp[i];
        while(*ptrTgt2++=*ptrTgt++=*ptrSrc++); // result = sum, fib(i) = sum
    }
    done=0;
    firsttime=1;
    while(!done)
    {
        count = 0;
        scanf("%s %s",&a_fib,&b_fib);
        if((a_fib[0] =='0') && (b_fib[0]=='0'))
        {
            done=1;
        }
        else
        {
            if(compareBigInteger(0,'c')==EQ)
            {
                found = 0;
                i=2;
                while(i<=fib)
                {
                    eqA = compareBigInteger(i,'a');
                    if(eqA==EQ)
                    {
                        found = 1;
                        i = MAX_SIZE;
                    }
                    else
                    {
                        i++;
                    }
                }
                if(found)count=1;
            }
            else
            {
                i=2;
                while(i<=fib)
                {
                    eqA = compareBigInteger(i,'a');
                    if(eqA==LT)
                    {
                        i++;
                    }
                    else
                    {
                        j = i;
                        i=MAX_SIZE;
                        count=1;
                    }
                }

                while(j<=fib)
                {
                    eqB = compareBigInteger(j,'b');
                    if(eqB==LT)
                    {
                        j++;
                        count++;
                    }
                    else
                    {
                        if(eqB==GT)
                        {
                            j--;
                            count--;
                        }
                        j=MAX_SIZE;
                    }
                }
            }
            if(firsttime)
            {
                printf("%d",count);
                firsttime=0;
            }
            else
            {
                printf("\n%d",count);
            }
        }
    }
    /* Code you want timed here */
    /*printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);*/
    return 0;
}

int add(void)
{
    int a;
    int b;
    int tot,u,carry;
    int i,j,k,len1;

    if(firsttime)
    {
        sum[0] = '0';
        sum[1] = '\0';
        firsttime=0;
        return 0;
    }

    i = strlen(result) - 1;
    j = strlen(prev) - 1;

    k = 0;
    carry =0;
    while(i >= 0)
    {
        a = result[i] - '0';
        if(j >= 0)
        {
            b = prev[j] - '0';
            j--;
        }
        else
        {
            b = 0;
        }
        tot = a + b + carry;
        if(tot>=10)
        {
            u = tot%10;
            carry = tot/10;
            sum[k] = u + '0';
            sum[k+1] = carry + '0';
        }
        else
        {
            sum[k] = tot + '0';
            carry = 0;
        }
        k++;
        i--;
    }
    sum[k+carry] ='\0';
    len1 = strlen(sum) - 1;
    for(k=0;k<=len1/2;k++)
    {
        a = sum[k];
        sum[k] = sum[len1-k];
        sum[len1-k] = a;
    }
    return 1;
}

/*
Returns 1 if Lookup[i] > val
       -1 if Lookup[i] < val
       0 if equal
*/

int compareBigInteger(int k,char ch)
{
    int len1;
    int len2;
    int i,there_is_a_match,retval=0;
    char *ptr1,*ptr2;

    len1 = strlen(LookUpTable.LookUp[k]);
    if(ch =='a')
    {
        len1 = strlen(LookUpTable.LookUp[k]);
        len2 = strlen(a_fib);
        ptr1 = LookUpTable.LookUp[k];
        ptr2 = a_fib;
    }
    else if(ch=='b')
    {
        len1 = strlen(LookUpTable.LookUp[k]);
        len2 = strlen(b_fib);
        ptr1 = LookUpTable.LookUp[k];
        ptr2 = b_fib;
    }
    else
    {
        len1 = strlen(a_fib);
        len2 = strlen(b_fib);
        ptr1 = a_fib;
        ptr2 = b_fib;
    }

    if(len1>len2) // value is > than lookuptable value
    {
        retval = GT;
    }
    else if(len1==len2) // the lengths are equal
    {
        // now compare the first digit of both if the first digit is same
        // then compare the next digit, which tells us if
        // the BigInteger_curr_row[k] is greater than ten_raised_to_60
        i = 0;
        there_is_a_match = 1;
        retval = 0;
        while(there_is_a_match && (i<len1))
        {
           if( (ptr1[i] == ptr2[i]) && (retval==EQ) )
           {
               retval = EQ; // number is equal so we reach last row
               i++; // continue comparing
           }
           else
           {
               if(ptr1[i] > ptr2[i])
               {
                   there_is_a_match = 0; // number is greater so we reach last row
                   retval = GT;
               }
               else
               {
                   there_is_a_match = 0;
                   retval = LT; // number is smaller so continue
               }
           }
        }
    }
    else
    {
        retval = LT;
    }
    return retval;
}
[/code]
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

User avatar
mrunmoy
New poster
Posts: 17
Joined: Mon Apr 09, 2007 3:11 pm
Location: India
Contact:

help me find the bug

Post by mrunmoy » Fri Dec 28, 2007 11:45 pm

here are the test cases which my code passes:-
10 100
1234567890 9876543210
3 5
5 8
0 1
1 2
0 2
0 7
298611126818977066918552 483162952612010163284885
1 36726740705505779255899443
8 12
8 13
1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
21 1
1 1
1 2
10 100
100 1000
5000 9000
1234000 123456000
5567 900000000
34556 10000000000000
43324234 85675676576575675675
8678678 345345345345345345353453453
235432435425 4364364653453646353643645656345646345
1 100000000000000000000000
234134 454765765674567457645
123421341234234 3465546345465634546564636
453643644654656645 45645465645465564645465654465465645
1 2
1 5
5 5
6 7
4 5
1 1
334 45564645
4356 56765878768787678768657856785576
23545 6547657457665
234535 46765758908765432
12 500000000000
45 9000000000000000000000000000000000
2354 566546456456456746545765464564
0 0
Here is the output
5
4
2
2
1
2
2
4
2
123
1
2
483
0
1
2
5
5
1
10
25
40
59
94
120
110
73
50
81
2
4
1
0
1
1
25
134
40
54
51
155
127
Best Regards,
Mrunmoy.

I belong to { IDIOTS }
IDIOTS - Intelligent Dynamic & Innovative On-The-Spot!

Sayeef
New poster
Posts: 12
Joined: Sun Jun 18, 2006 3:06 am

I get WA for this problem

Post by Sayeef » Tue Jan 01, 2008 7:12 am

I keep Getting WA for this problem plz help

Code: Select all

#include<stdio.h>
#include<string.h>
#define MAX 1050
int cmp(char a[],char b[] )
{
	int al,bl;
	al=strlen(a);
	bl=strlen(b);
	if(al!=bl)
		return al-bl;
	for(int i=0;a[i];i++)
	{
		if(a[i]!=b[i])
			return a[i]-b[i];
	}
	return 0;
}
void strev(char *a,int len)
{
	int i,j;
	char tmp;
	j=len;
	for(i=0,j=len-1;i<len/2;i++,j--)
	{
		tmp=a[i];
		a[i]=a[j];
		a[j]=tmp;
	}
}

class bigInt
{
public:
	char *val;
void set_val(const char *c)
	{
		int len;
		len=strlen(c);
		val=new char[len+1];
		strcpy(val,c);
	}
};

bigInt fib[5001];


void add(char a[],char b[],bigInt &c)
{
	int i,j,p,lena,lenb,ad=0;
	char tc[MAX]={'\0'}; 
	//strcpy(ta,a);
	//strcpy(tb,b);
	//strcpy(tc,c);

	lena=strlen(a);
	lenb=strlen(b);
	
	strev(a,lena);
	strev(b,lenb);
	for(i=0,j=0,p=0;;p++)
	{
		
		if(a[i]=='\0'&&b[j]=='\0')
		{		
			if(ad!=0)
				tc[p]=ad+48;
			int lenc=strlen(tc);
			strev(tc,lenc);
			c.set_val(tc);
			return;
		}
		
		else if(a[i]=='\0')
		{
			ad=(b[j++]-'0') + ad;
			tc[p]=ad%10+48;
			ad=ad/10;
			
		}
		else if(b[j]=='\0')
		{
			ad=(a[i++]-'0') + ad;
			tc[p]=ad%10+48;
			ad=ad/10;
		}
		else
		{
			ad=(a[i++]-'0') + (b[j++]-'0')+ad;
			tc[p]=ad%10+48;
			ad=ad/10;	
		}

	}
}

void fib_gen()
{
	int i;
	fib[0].set_val("0");
	fib[1].set_val("1");
	fib[2].set_val("2");
	char ta[1050],tb[1050];  
	for(i=3;i<600;i++)
	{
		
		strcpy(ta,fib[i-1].val);
		strcpy(tb,fib[i-2].val);
		add(ta,tb,fib[i]);
	
	}
}


int main()
{
	fib_gen();
	int n;
	char a[150]={"\0"},b[150]={'\0'};
	while(scanf("%s %s",a,b)&&(strcmp(a,"0")||strcmp(b,"0")))
	{
			int i=0,s_loc=0,p,fl=0;
			while(cmp(fib[i].val,a)<0)
				i++;
			s_loc=i;
			i=0;
			while(cmp(fib[i].val,b)<=0)
				i++;
			printf("%d\n",i-s_loc);
			
		
	}
return 0;
}

zyxw
New poster
Posts: 24
Joined: Sat Mar 22, 2008 5:49 am
Location: Chennai
Contact:

Re: 10183 - help me find the bug

Post by zyxw » Thu May 29, 2008 8:15 am

To mrunmoy...

for this input:

Code: Select all

 1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 
my AC code prints:

Code: Select all

481
:wink:
I am not totally useless, because I can still be used as a bad example :P

Post Reply

Return to “Volume 101 (10100-10199)”