fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll L, R;
  5. vector <ll> weights;
  6. void read() {
  7.     cin >> L >> R;
  8. }
  9. void precompute() {
  10.     weights.push_back(1);
  11.     weights.push_back(2);
  12.     while (weights.back() <= 1e18) {
  13.         int sz = weights.size();
  14.         weights.push_back(weights[sz-1] + weights[sz-2]);
  15.         if (weights.back() > 1e18) break;
  16.     }
  17. }
  18. void solve() {
  19.     for (ll i = L; i<=R; ++i) {
  20.         vector <ll> left, right;
  21.  
  22.         ll x = i;
  23.         ll closest = weights[0];
  24.         while (x != 0) {
  25.             for (ll w : weights) {
  26.                 if (abs(w - abs(x)) < abs(closest - abs(x))) {
  27.                     closest = w;
  28.                 }
  29.             }
  30.             if (x > 0) {
  31.                 right.push_back(closest);
  32.                 x -= closest;
  33.             } else {
  34.                 left.push_back(closest);
  35.                 x += closest;
  36.             }
  37.         }
  38.  
  39.         left.push_back(i);
  40.         sort(left.rbegin(), left.rend());
  41.         sort(right.rbegin(), right.rend());
  42.  
  43.         cout << left.size() + right.size() << "\n";
  44.  
  45.         cout << left.size();
  46.         for (ll x : left) cout << " " << x;
  47.         cout << "\n" << right.size();
  48.         for (ll x : right) cout << " " << x;
  49.         cout << "\n";
  50.     }
  51. }
  52. int main() {
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(0); cout.tie(0);
  55.  
  56.     read();
  57.     precompute();
  58.     solve();
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1 0
0
https://ideone.com/3iOjNB
language:
C++ (gcc 8.3)
created:
3 days 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!