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

ante0001
New poster
Posts: 1
Joined: Wed Oct 31, 2001 2:00 am
Location: Ante

10183 - How Many Fibs?

Post by ante0001 » Tue Nov 27, 2001 6:22 pm

what are the fib. numbers ? Is this correct
0,1,1,2,3,5,8,13,21 ...

asyukri10
New poster
Posts: 5
Joined: Wed Nov 28, 2001 2:00 am
Location: Malaysia
Contact:

Post by asyukri10 » Thu Nov 29, 2001 12:58 am

Try this,
1,2,3,5,8,13,...

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

10183(How many Fibs)

Post by lowai » Mon Nov 04, 2002 4:30 am

i got WA.
i calc first 480 fibonacci numbers at first.
what's the trick here?
[pascal]
var
fib : array[1..480]of string[101];
i, j, s, t, code : integer;
a, b : string;

function geq(x, y : string) : boolean;
var i : integer;
begin
if length(x) < length(y) then geq := false
else if length(x) > length(y) then geq := true
else
begin
for i := 1 to length(x) do
if x < y then
begin geq := false; exit; end
else if x > y then
begin geq := true; exit; end;
geq := true;
end;
end;

begin
fib[1] := '1';
fib[2] := '1';
for i := 3 to 480 do
begin
s := 0;
a := fib; if length(a) < length(fib) then a := '0' + a;
for j := length(fib) downto 1 do
begin
t := ord(fib[i - 1, j]) + ord(a[j]) + s - 96;
fib := chr(t mod 10 + 48) + fib;
s := t div 10;
end;
if s > 0 then fib := chr(s + 48) + fib[i];
end;
readln(b);
while true do
begin
i := pos(' ', b);
a := copy(b, 1, i - 1);
delete(b, 1, i);
while b[1] = ' ' do delete(b, 1, 1);
if (a = '0') and (b = '0') then break;

for i := 1 to 480 do
if geq(fib[i], a) then break;
for j := 480 downto 1 do
if geq(b, fib[j]) then break;
writeln(j - i + 1);
readln(b);
end;
end.
[/pascal]

Moinul(AUST)
New poster
Posts: 11
Joined: Tue Dec 10, 2002 11:40 am
Location: Dhaka, Bangaldesh
Contact:

Post by Moinul(AUST) » Thu Dec 12, 2002 8:48 pm

What is the Problem with 10183?
Is there anything exceptional case in the problem? I have used the fibonacci series from 1 2 3 5 8 13 ... and got WA.

Since the input range is a ,b <=10^100... I used string operation to generate all the first 5000 fibo. (allthough 5000th fibo is of 1045 digit long and donot require such long number of fibo for this problem)

But, getting WA. I used Long double to read the range.....

Then, I have tried with only long double to generate first 1000 fibo and still getting WA.

NB: My fibo() function using string addition works correctly... I have made "Fibonacci Freeze problem" accepted using this function.

Here is my second code ---

#include<stdio.h>

long double fibs[1000];


void fibo1()
{
long double a,b,c;
int i=2,count=2;

fibs[0]=1;
fibs[1]=2;
a=1;
b=2;
for(;;)
{
if (count>1000) break;
c=a+b;
fibs=c;
++i;
a=b;
b=c;
count++; }

}

void main()
{
int count;
int i;
long double from,to;

fibo1();

while(1)
{
scanf("%Lf%Lf",&from,&to);
if (from==to && from==0 ) break;

count=0;
long double aa;
for(i=0;i<1000; ++i)
{
if (fibs<from) continue;
aa=fibs;
if(aa>to) break;
{
count++;
}
}

printf("%d\n",count);


}

}

If anyone have any suggestions, pls help

-Moinul

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Dec 14, 2002 7:44 am

Well... I don't understand how you want to get AC if you read input in long double. If long double could keep so much digit then so much problems would become so easy... :lol: You should read input as strings and compare them by hand.

Try it and get AC!!!

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Dec 16, 2002 6:31 am

i have try it with the formula fn=(1+5^1/2)....
but i got WA for all time.
can't the problem be solved by the way?
really i need string?
---thanks.
"Everything should be made simple, but not always simpler"

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Mon Dec 16, 2002 8:18 am

No, unfortunately the problem cannot be solved by the way, as you can't properly check whether a number is in or out the given interval. Long double can't keep 100 digits but even the last digit may be very important to say if one number is greater than the other or not.

So, you really MUST use long arithmetic operations, or strings as you call it. :(

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Dec 18, 2002 10:42 am

do you want tot say that i should use string to produce fib no.? :oops:
"Everything should be made simple, but not always simpler"

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Thu Dec 19, 2002 9:56 am

You should use strings both for calculating fibs and during comparisons.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Thu Dec 19, 2002 8:52 pm

Can anyone confirm the following input:
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
0 0
gives the following output:
5
4
2
2
1
2
2
4
2
123
1
2
483
7

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Thu Dec 19, 2002 9:03 pm

Never mind. If I put the right problem number on my submissions then its no longer WA !!!!!!!! Ho hum, how many times have I done that now ???? Anyway, to other people trying to solve this one the output above is correct ;)

Moinul(AUST)
New poster
Posts: 11
Joined: Tue Dec 10, 2002 11:40 am
Location: Dhaka, Bangaldesh
Contact:

WA

Post by Moinul(AUST) » Thu Dec 26, 2002 8:20 pm

I am always getting WA... Tested my program with Caesum's input. It seems to give correct result.

This is what i did to compare the pre-generated fibonacci numbers from the String array.


//used 'from' and 'to' string to read the range.
// swaping the number range if from > to ;
if (strlen(from)>strlen(to) || strlen(from)==strlen(to) && strcmp(from,to ==1)
{
strcpy(temp1,from);
strcpy(from,to);
strcpy(to,temp1);
}
lenf=strlen(from);
lent=strlen(to);

int temp;
int total=0;
for(i=0; i<5004; ++i) //5004 fibo in the array
{
temp=strlen(fibarr);
if (temp>lenf || strcmp(fibarr,from)==1 && lenf==temp|| strcmp(fibarr,from)==0 && lenf==temp)
{
if (lent==temp )
{
if (strcmp(fibarr,to)==-1 || strcmp(fibarr,to)==0)
{
total++; continue;
}
}
else if (temp <lent)
{ total++; }
else break;
}

} //end for

Any suggestion from anybody?

-Moinul

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Fri Dec 27, 2002 8:55 am

I have two questions to you. First - why you swap from and to if from>to? My program outputs 0 in this case. And another question - are you sure that constructions like
strcmp(fibarr,from)==1

or
strcmp(fibarr,to)==-1

work correctly. I guess that is not safe, as it seems to me that strcmp() may return different integers, not only +/-1. You should better write this way

Code: Select all

strcmp(fibarr[i],from)>0
Well, I don't know if I'm right or not, but try it.

Moinul(AUST)
New poster
Posts: 11
Joined: Tue Dec 10, 2002 11:40 am
Location: Dhaka, Bangaldesh
Contact:

Post by Moinul(AUST) » Sat Dec 28, 2002 1:54 pm

Thanks to Andrey Mokhov for pointing out about the Strcmp() return values. Yes, Strcmp() doesn't always return +/- 1

So, I have changed the strcmp() values to >0 and <0 and got 'AC'.
I have left the swap (from,to) option unchanged and got AC, which means , the Judge input doesn't have any value where (from > to) :D

Once again Thanks to Andrey Mokhov and all other for their posts.

-Moinul

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

10183: why Compile error?

Post by razibcse » Tue Feb 18, 2003 2:27 am

I generated first 500 Fibonacci numbers first, coz 500th fib. number
has 105 digits,more than needed for this prog.
then I tried to find the number of fibs between the range given as strings...

but it gets CE always...

What's the matter, guys?
Pls help me out..

Here's my code:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 5010
#define MAXSZ 200

char *str_add(char fib1[],char fib2[],long len1,long len2);
long check_length(char fibonacci[],char range[],long len);

char *fib[MAX],A[MAXSZ],B[MAXSZ];
void main()
{

long i,j,len1,len2,A_len,B_len,fib_len,check;
long start,end,dif;
char *ptr,fib1[MAXSZ],fib2[MAXSZ];

for(i=0;i<3;i++)
  fib[i]=(char *)malloc(3*sizeof(char));

fib[0][0]='1';
fib[0][1]='\0';
fib[1][0]='1';
fib[1][1]='\0';
fib[2][0]='2';
fib[2][1]='\0';

 for(i=3;i<=500;i++)
    {
    fib[i]=(char *)malloc(MAXSZ*sizeof(char));

    len1=strlen(fib[i-1]);
    len2=strlen(fib[i-2]);
    strcpy(fib1,fib[i-1]);
    strcpy(fib2,fib[i-2]);
    ptr=str_add(fib1,fib2,len1,len2);
    strcpy(fib[i],ptr);
    }


for(;;)
  {
  scanf("%s %s",A,B);
  if(!strcmp(A,"0") && !strcmp(B,"0"))
     break;

  A_len=strlen(A);
  B_len=strlen(B);

  start=0;
  end=0;
  for(i=1;i<=500;i++)
      {
      fib_len=strlen(fib[i]);
      if(fib_len<A_len)
         continue;

      if(fib_len==A_len)
          {
          check=check_length(fib[i],A,fib_len);
          if(check>=0)
              {
              start=i;
              break;
              }
          else if(check<0)
              continue;

          }
      if(fib_len>A_len)
       start=i;
      break;
      }

  for(j=start;j<=500;j++)
      {

      fib_len=strlen(fib[j]);
      if(fib_len<B_len)
           continue;

      if(fib_len==B_len)
           {
           check=check_length(fib[j],B,fib_len);
           if(check==0)
               {
		         end=j;
               break;
               }
           else if(check>0)
               {
               end=j-1;
               break;
               }

           else if(check<0)
               continue;

           }

       if(fib_len>B_len)
        end=j-1;
       break;
       }
  dif=end-start+1;
  printf("%ld\n",dif);

  }
}

char *str_add(char fib1[],char fib2[],long len1,long len2)
{

long sum,max,min,dif,a,re,qu,i,j,k,x,y;
char *result;

result=(char *)malloc(MAXSZ*sizeof(char));

if(len1>=len2)
 {
 max=len1;
 min=len2;
 dif=max-min;

 for(a=min-1;a>=0;a--)
   fib2[a+dif]=fib2[a];
   fib2[max]='\0';

 for(a=0;a<dif;a++)
   fib2[a]='0';

 }
else if(len1<len2)
 {
 max=len2;
 min=len1;
 dif=max-min;

 for(a=min-1;a>=0;a--)
   fib1[a+dif]=fib1[a];
   fib1[max]='\0';

 for(a=0;a<dif;a++)
   fib1[a]='0';

 }


qu=0;
i=MAXSZ-1;
for(a=max-1;a>=0;a--)
  {
  sum=qu+(fib1[a]-48)+(fib2[a]-48);

  if(sum>=10)
    {
    qu=sum/10;
    re=sum%10;
    }
  else if(sum<10)
    {
    qu=0;
    re=sum;
    }
  result[i--]=(char)(re+48);
  if(a==0 && qu!=0)
    {
    for(;;)
        {
        x=qu/10;
        y=qu%10;
        result[i--]=char(y+48);
        if(x==0) break;
        qu=x;
        }
    }
  }
j=i+1;
k=MAXSZ-1-j;

for(i=j;i<=MAXSZ;i++)
  result[i-j]=result[i];

result[k+1]='\0';

return result;
}

long check_length(char fibonacci[],char range[],long len)
{
long a,mark=0;
if(!strcmp(fibonacci,range)) return 0;
for(a=0;a<len;a++)
  {
  if(fibonacci[a]>range[a])
     {
     mark=1;
     break;
     }
  else if(fibonacci[a]<range[a])
     {
     mark=-1;
     break;
     }
  }
return mark;
}

Post Reply

Return to “Volume 101 (10100-10199)”