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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int max_size = 100;



int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    uint64_t k;
    cin>>k;

    if (k==1)
    {
        cout<<2<<endl;
        cout<<"2 -1"<<endl;
        cout<<"-1 -1"<<endl;
        return 0;
    }

    vector<pair<int, int>> polaczenia(max_size, make_pair(-1,-1));
    vector<uint64_t> zliczenia_drog(max_size, 0); // ile drog od i-tego wierzcholka do ostatniego

    // budowanie grafu:

    zliczenia_drog.back() = 1; // ostatni polaczony niepolaczony - 1 droga

    polaczenia[max_size-2] = make_pair(max_size, -1); // przedostatni polaczony tylko z ostatnim - 1 droga
    zliczenia_drog[max_size-2] = 1;

    int start=max_size;

    for (int ii=max_size-3; ii>=0; ii--)
    {
        int Nr = ii+1; //nr wierzchołka - ideksy w tablicy od 0, numeracja w grafie od 1!
        uint64_t L_drog = zliczenia_drog[ii+1] + zliczenia_drog[ii+2]; // Fibonacci :)
        if (L_drog <=k)
        {
            zliczenia_drog[ii] = L_drog;
            polaczenia[ii] = make_pair(Nr+1, Nr+2);
        }
        else // polaczenie z mniejszymi liczbami Fibonacciego
        {
            auto it0 = zliczenia_drog.begin()+ii+1;
            auto it = lower_bound(it0, zliczenia_drog.end(), k-zliczenia_drog[ii+1], greater<int>());
            int ind2 = it - zliczenia_drog.begin();
            int Nr2 = ind2+1;
            zliczenia_drog[ii] = zliczenia_drog[ii+1] +zliczenia_drog[ind2];
            polaczenia[ii] = make_pair(Nr+1, Nr2);
        }
        if (zliczenia_drog[ii]==k)
        {
            start = ii;
            break;
        }
    }

    // usuniecie niepotrzebnych wierzcholkow i wypisanie wyniku
    cout<< max_size-start<<endl;
    for (int ii=start; ii<max_size; ii++)
    {
        if (polaczenia[ii].first >0)    // nie zmieniac -1!
            polaczenia[ii].first -=start;
        if (polaczenia[ii].second >0)
            polaczenia[ii].second -=start;
        cout <<polaczenia[ii].first<< ' '<<polaczenia[ii].second<<endl;
    }


    return 0;
}