Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=50000;
  oo=1000111000111000111;
var
  f1,f2:text;
  sl,test,hsize:longint;
  n:qword;
  h,a,x:array[1..MAXN] of qword;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure swap(var a,b:qword); inline;
var
  temp:qword;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (h[j+1]<h[j]) then inc(j);
      if (h[j]<h[i]) then swap(h[i],h[j]);
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (h[i]<h[j]) do
    begin
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:qword); inline;
begin
  inc(hsize); h[hsize]:=u;
  upHeap(hsize);
end;
procedure pop(var u:qword); inline;
begin
  u:=h[1]; swap(h[1],h[hsize]); dec(hsize);
  downHeap(1);
end;
function get(u:qword):qword; inline;
var
  x1,x2:qword;
begin
  if (u=0) then exit(0);
  if (u=1) then exit(1);
  if (u=2) then exit(1);
  while u mod 2=0 do u:=u>>1; u:=u>>1;
  x1:=1; x2:=1;
  while (u>=2) do
    begin
      if u mod 2=0 then x1:=x1+x2 else x2:=x2+x1;
      u:=u>>1;
    end;
  exit(x1+x2);
end;
procedure init;
var
  u,v:qword;
  ln:qword;
begin
  hsize:=1; h[1]:=1; ln:=0; sl:=0;
  while hsize>0 do
    begin
      pop(u); v:=get(u);
      while (hsize>0) and (h[1]=u) do pop(u);
      if v>ln then
        begin
          inc(sl); a[sl]:=u; x[sl]:=v; ln:=v;
          if u<<1-1<=oo then push(u<<1-1);
          if u<<1+1<=oo then push(u<<1+1);
          if u<<2-1<=oo then push(u<<2-1);
          if u<<2+1<=oo then push(u<<2+1);
        end;
    end;
end;
procedure solve;
var
  l,r,mid,kq:longint;
begin
  l:=1; r:=sl;
  repeat
    mid:=(l+r)>>1;
    if a[mid]<=n then
      begin
        kq:=mid;
        l:=mid+1;
      end
    else r:=mid-1;
  until l>r;
  writeln(f2,x[kq]);
end;
begin
  openF;
  init;
  read(f1,test);
  for test:=1 to test do
    begin
      read(f1,n);
      solve;
    end;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include <conio.h>

using namespace std;

typedef unsigned long long ul;
ul fibo[65],n,N,c1,c2,temp;
ul a[11111], f[11111];
#define lon 1ll << 60

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

ul fx(ul x)
{
    if(x == 0) return 0;
    while(x%2==0) x=x>>1;
    if(x== 1) return 1;
    ul x1 = 1,x2=1;
    x = x>>1;
    while (x>=2) {
       if (x%2 ==1) x2+=x1; else x1+=x2;
       x = x>>1;
    }
    return x1+x2;    
}

   set<ul> S;

int main()
{
  //  OPEN();
    fibo[0] = 0; fibo[1] = 1;
    for(int i = 2;i<=64;i++)
         fibo[i] = fibo[i-1]+fibo[i-2];

    int size = 0;
    f[++size] = 0;
    a[size] = 0;

    set<ul>:: iterator it;
    S.insert(1);
    for(it = S.begin();it != S.end();it++)
    {
         N = *it;
         n = N;
         if(n >= lon) break;
         ul KQ = 0;
         for(int i = 0;n>0;i++,n/=2)
         {
             if(n%2==1)
             {
                  c1 = fx(n-1); c2 = fx(n);
                  if(c1<c2) {temp = c1; c1 = c2;c2 = temp;}
                  if(KQ<c1*fibo[i+1]+c2*fibo[i])
                      KQ = c1*fibo[i+1]+c2*fibo[i];
             }
         }
         if(KQ > f[size]){
            f[++size] = KQ;
            a[size] = N;
          //  printf("%llu ....\n",n);
            S.insert(N * 2 - 1);
            S.insert(N * 2 + 1);
            S.insert(N * 4 - 1);
            S.insert(N * 4 + 1);
         }
    }
    int test;
    scanf("%d", &test);
    while(test--){
        scanf("%llu", &n);
        int u = 0, v = size + 1, r;
        while(u < v){
            r = (u + v) / 2;
            if(a[r] <= n) u = r + 1;
            else v = r;
        }
        printf("%llu\n", f[u - 1]);
    }
   // printf("%d\n",size);
    //getch();
}

Code mẫu của ll931110

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

long long calc(long long x)
{
    if (x < 2) return x;
    while (!(x & 1)) x >>= 1;
    if (x < 3) return 1;

    long long y = 1, z = 1;
    for (x >>= 1; x > 1; x >>= 1)
      (x & 1)?(z += y):(y += z);
    return y + z;
};

int main()
{
    int inf,sup,med,nTest;
    long long ret;

//    freopen("mr.in","r",stdin);
//    freopen("mr.o1","w",stdout);

    priority_queue<long long> q;
    vector< pair<long long, long long> > v;

    q.push(-1);
    v.push_back(make_pair(0,0));

    while (!q.empty())
    {
        long long u = -q.top();
        q.pop();

        if (u != v[v.size() - 1].first)
        {
          long long t = calc(u);
          if (t > v[v.size() - 1].second) 
          {
                v.push_back(make_pair(u,t));
                if (4 * u + 1 <= 1e18) q.push(-(4 * u + 1));
                if (4 * u - 1 <= 1e18) q.push(-(4 * u - 1));
                if (2 * u + 1 <= 1e18) q.push(-(2 * u + 1));
                if (2 * u - 1 <= 1e18) q.push(-(2 * u - 1));
          };
        };
    };

    long long n;    
    scanf("%d\n", &nTest);
    do
    {
        nTest--;
        scanf("%lld\n", &n);
        inf = 0; sup = v.size() - 1; ret = 0;
        while (inf <= sup)
        {
            med = (inf + sup)/2;
            if (v[med].first <= n)
            {
                ret = v[med].second;
                inf = med + 1;
            }
            else sup = med - 1;
        };        
        printf("%lld\n", ret);
    }
    while (nTest > 0);
};