fork download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3. using namespace std;
  4.  
  5. int binarysearch(unsigned long long a[], unsigned long long n)
  6. {
  7.     int mid, i=0, ll=0, ul=89;
  8.     while(1)
  9.     {
  10.         mid=(ll+ul)/2;
  11.         if(n>a[mid])
  12.         {
  13.             ll=mid;
  14.             if(ll+1 == ul) {i=ul; break;}
  15.         }
  16.         else if(n<a[mid])
  17.         {
  18.             ul=mid;
  19.             if(ul-1 == ll) {i=ul; break;}
  20.         }
  21.         else if(n==a[mid]) {i=mid+1; break;}
  22.     }
  23.     i-=3;
  24.     return i;
  25. }
  26.  
  27. unsigned long long fib[89] = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,
  28. 196418ull,317811ull,514229ull,832040ull,1346269ull,2178309ull,3524578ull,5702887ull,9227465ull,14930352ull,24157817ull,39088169ull,63245986ull,102334155ull,165580141ull,
  29. 267914296ull,433494437ull,701408733ull,1134903170ull,1836311903ull,2971215073ull,4807526976ull,7778742049ull,12586269025ull,20365011074ull,32951280099ull,
  30. 53316291173ull,86267571272ull,139583862445ull,225851433717ull,365435296162ull,591286729879ull,956722026041ull,1548008755920ull,2504730781961ull,
  31. 4052739537881ull,6557470319842ull,10610209857723ull,17167680177565ull,27777890035288ull,44945570212853ull,72723460248141ull,117669030460994ull,
  32. 190392490709135ull,308061521170129ull,498454011879264ull,806515533049393ull,1304969544928657ull,2111485077978050ull,3416454622906707ull,
  33. 5527939700884757ull,8944394323791464ull,14472334024676221ull,23416728348467685ull,37889062373143906ull,61305790721611591ull,99194853094755497ull,
  34. 160500643816367088ull,259695496911122585ull,420196140727489673ull,679891637638612258ull,1100087778366101931ull};
  35.  
  36. int main()
  37. {
  38. 	int testcases;
  39. 	cin>>testcases;
  40.     unsigned long long N,output=0;
  41.     while(testcases--)
  42.     {
  43.     	cin>>N;
  44.     	output = binarysearch(fib,N);
  45.     	cout<<output<<endl;
  46.     }
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0s 3100KB
comments (?)
stdin
copy 
3
4
5
8
stdout
copy 
2
3
4
https://ideone.com/xAklrg
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!