1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>

using namespace std;

#define MAXFIBO 46
#define MAXV 100

int F[MAXFIBO];
bool K[MAXFIBO];

void init_fibo() {
  F[0] = 0;
  F[1] = 1;
  for (int i = 2; i < MAXFIBO; ++i) {
    F[i] = F[i - 1] + F[i - 2];
  }
}

int find_largest_fibo(int n) {
  int i;
  for (i = MAXFIBO - 1; i >= 0 && F[i] > n; --i)
    ;
  return i;
}

void encode_fibo(int k) {
  int i;
  for (i = 0; i < MAXFIBO; ++i) {
    K[i] = false;
  }
  while (k > 0) {
    i = find_largest_fibo(k);
    K[i - 2] = true;
    k -= F[i];
  }
}

int main(int argc, char *argv[]) {
  int i, j, k;

  ios_base::sync_with_stdio(0);
  cin >> k;
  init_fibo();
  encode_fibo(k);

  cout << MAXV << endl;
  // binary tree large enough for all significant digits
  for (j = 1; j <= MAXFIBO / 2; ++j) {
    cout << j * 2 << " " << j * 2 + 1 << endl;
  }

  // significant digits
  bool do_endl = false;
  for (i = 0; i < MAXFIBO; ++i) {
    if (K[i]) {
      cout << MAXV - i - 1;
      if (!do_endl) {
        do_endl = true;
        cout << " ";
      } else {
        do_endl = false;
        cout << endl;
        ++j;
      }
    }
  }

  // padding
  while (j < MAXV - MAXFIBO) {
    cout << -1;
    if (!do_endl) {
      do_endl = true;
      cout << " ";
    } else {
      do_endl = false;
      cout << endl;
      ++j;
    }
  }

  // digits
  while (j <= MAXV - 2) {
    cout << j + 1 << " " << j + 2 << endl;
    ++j;
  }
  cout << j + 1 << " " << -1 << endl;
  cout << -1 << " " << -1 << endl;

  return 0;
}