fork(2) download
copy 
  1. #include <algorithm>
  2. #include <cstdint>
  3. #include <iostream>
  4. #include <limits>
  5. #include <vector>
  6.  
  7. int main() {
  8.   // Calculate fibonacci numbers.
  9.   std::vector<std::int64_t> fib_nums;
  10.   std::int64_t a = 0;
  11.   std::int64_t b = 1;
  12.   fib_nums.push_back(a);
  13.   fib_nums.push_back(b);
  14.   for (;;) {
  15.     if (a > std::numeric_limits<std::int64_t>::max() - b) {
  16.       break;
  17.     }
  18.     std::int64_t c = a + b;
  19.     fib_nums.push_back(c);
  20.     a = b;
  21.     b = c;
  22.   }
  23.  
  24.   // Num test cases.
  25.   std::size_t p;
  26.   std::cin >> p;
  27.  
  28.   while (p--) {
  29.     std::int64_t k;
  30.     std::cin >> k;
  31.  
  32.     std::size_t n = 0;
  33.     while (k > 0) {
  34.       auto lower_bound = std::lower_bound(fib_nums.begin(), fib_nums.end(), k);
  35.       // a < k <= b
  36.       std::int64_t a = *(lower_bound - 1);
  37.       std::int64_t b = *lower_bound;
  38.       // greedy
  39.       k = std::min(k - a, b - k);
  40.       ++n;
  41.     }
  42.  
  43.     std::cout << n << '\n';
  44.   }
  45.  
  46.   return 0;
  47. }
  48.  
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
4
10
19
17
1070
stdout
copy 
2
2
3
4
https://ideone.com/m3d7gb
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!