#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; }
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; } |