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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <vector>
using namespace std;

vector<int> fib;
void gen_fib()
{
    fib.push_back(0);
    fib.push_back(1);
    for(int i=0; i<45; ++i)
    {
        int x = fib[fib.size()-1];
        int y = fib[fib.size()-2];
        fib.push_back(x+y);
    }
}

vector<pair<int,int>> rozklad(int k)
{
    vector<pair<int,int>> res;
    while(k)
    {
        int i=0;
        while(fib[i]<=k)
        {
            ++i;
        }
        //cout << fib[i-1] << endl;
        res.push_back(make_pair(i-1,fib[i-1]));
        k -= fib[i-1];
        //cout << "k = " << k << endl;
        //system("pause");
    }
    return res;
}

void print(vector<pair<int,int>> g)
{
    cout << "Krawedzie:" << endl;
    for(int i=0; i<g.size(); ++i)
    {
        cout << "(" << g[i].first << "," << g[i].second << ")" << endl;
    }
    cout << "---------------------------" << endl;
}

void swap_1n(vector<pair<int,int>>& g, int n)
{
    for(int i=0; i<g.size(); ++i)
    {
        if(g[i].first == 1 || g[i].first == n)
            g[i].first = n + 1 - g[i].first;

        if(g[i].second == 1 || g[i].second == n)
            g[i].second = n + 1 - g[i].second;
    }
}

void gen_output(vector<pair<int,int>> g, int n)
{
    vector<vector<int>> v(n+1);
    for(int i=0; i<g.size(); ++i)
    {
        int u = g[i].first;
        int w = g[i].second;
        v[u].push_back(w);
    }

    //dodaj minus jedynki
    for(int i=1; i<=n; ++i)
        while(v[i].size()<2)
            v[i].push_back(-1);

    //wypisz rozwiazanie
    cout << n << "\n";
    for(int i=1; i<=n; ++i)
    {
        cout << v[i][0] << " " << v[i][1] << "\n";
    }
}

int main()
{
    gen_fib();
    //cout << fib.back() << endl;
    int k;
    cin >> k;
    vector<pair<int,int>> roz = rozklad(k);
    //for(int i=0; i<roz.size(); ++i)
    //    cout << roz[i].first << "," << roz[i].second << ";  ";
    //cout << endl;

    //int v = roz[0].first + roz.size() - 1;
    //cout << v << endl;

    vector<pair<int,int>> g;

    g.push_back(make_pair(2,1)); // pierwsza krawedz

    for(int i=3; i<=roz[0].first; ++i)
    {
        g.push_back(make_pair(i,i-1));
        g.push_back(make_pair(i,i-2));
    }
    //print(g);

    for(int i=1; i<roz.size(); ++i)
    {
        int u = roz[0].first + i;
        int v = roz[i].first;
        g.push_back(make_pair(u,u-1));
        g.push_back(make_pair(u,v));
    }
    //print(g);
    //cout << "n=" << g.back().first << endl;

    int n = g.back().first;
    swap_1n(g, n);
    //print(g);

    gen_output(g, n);
}