10183 - How Many Fibs?

[ante0001]

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

[asyukri10]

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

[lowai]

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)]

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]

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... You should read input as strings and compare them by hand.

Try it and get AC!!!

[anupam]

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.

[Andrey Mokhov]

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]

do you want tot say that i should use string to produce fib no.?

[Andrey Mokhov]

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

[Caesum]

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]

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)]

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]

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)]

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)

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

-Moinul

[razibcse]

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;
}