AOI Study Hub

Appearance

Zeckendorf ​

Problem Statement ​

let be the zeckendorf representation of and

Subtask 1 ​

Since , we can solve each case by hand and hardcode the results.

  • Observation: , so at most 5 digits are needed for .
  • Strategy: brute force all possible binary strings of length , checking whether they correspond to valid Zeckendorf representations.
  • Complexity: for digits, which is feasible for .

Subtask 2 ​

We extend the idea of Subtask 1. Instead of checking all binary strings, we only generate valid ones via recursion.

  • Fact: the number of valid binary strings of length with no two consecutive s is (with our shifted definition).
  • Thus, the complexity is

Full Solution ​

We use a greedy approach:

  1. Given , find the largest Fibonacci number .
  2. Set digit , and update .
  3. Repeat until .

This procedure constructs the Zeckendorf representation of .

Proof of Correctness ​

Let be the largest Fibonacci number . Then:

  • By definition, .
  • Since , we have

Thus, after subtracting , the remainder is strictly smaller than , meaning we will never need .
This guarantees that the greedy algorithm avoids consecutive Fibonacci numbers and always produces a valid representation.

Uniqueness follows from the same inequality: if another representation existed with different largest Fibonacci number, it would contradict the maximality of .

Algorithm ​

  1. Precompute Fibonacci numbers up to the largest .
  2. For each query :
    • Start with the largest Fibonacci number .
    • Subtract it and mark its digit as .
    • Repeat until .
  3. Output the resulting binary string.

Complexity:

  • Precomputation: .
  • Each query: since each subtraction reduces by at least half in size.
  • Total: .

Implementation ​

cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<ll> fibo = {1, 2};

string zeckendorf(ll n)
{

   while(fibo.back() < n){
      fibo.push_back(fibo[fibo.size()-1] + fibo[fibo.size()-2]);
   }

   ll p = fibo.size() - 1;
   while(fibo[p] > n) p--;
   string res = "";
   while(p >= 0){
      if(fibo[p] <= n){
         res += "1";
         n -= fibo[p];
      }else{
         res += "0";
      }
      p--;
   }

   return res;
}

signed main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   ll q;
   cin >> q;
   while (q--)
   {
      ll n;
      cin >> n;
      cout << zeckendorf(n) << '\n';
   }
}