#include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; #define MF 44 vector<int> fibb(MF+1); struct node { int l, r; node(int a,int b): l(a), r(b) { } void print_rev(int n) { if (l == -1) cout << l; else cout << (n-l+1); cout << ' '; if (r == -1) cout << r; else cout << (n-r+1); cout << '\n'; } }; void fill_fib() { fibb[1] = 1; fibb[2] = 1; for (int k=3;k<=MF;k++) { fibb[k] = fibb[k-1] + fibb[k-2]; //cout << k << " " << fibb[k] << '\n'; } } stack<int> podziel_fibb(int k) { stack<int> res; int j = MF; vector<int> t; while (k > 0) { while (fibb[j] > k) j--; k -= fibb[j]; //cout << fibb[j] << " (" << j << ") "; t.push_back(j); } //cout << '\n'; for(int i=t.size()-1;i>=0;i--) res.push(t[i]); return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; if (n == 1) { cout << "2\n2 -1\n-1 -1\n"; return 0; } fill_fib(); stack<int> podzial = podziel_fibb(n); int mfb = podzial.top(); //cout << "mfb=" << mfb << "\n"; vector<node> sol; sol.push_back(node(-1,-1)); sol.push_back(node(1,-1)); int z = 3; while(z <= mfb) { sol.push_back(node(z-1,z-2)); z++; } int k = mfb; while(podzial.size() > 1) { int a = podzial.top(); podzial.pop(); int b = podzial.top(); podzial.pop(); k++; podzial.push(k); node q(a,b); sol.push_back(q); } node q(podzial.top(),-1); sol.push_back(q); cout << sol.size() << '\n'; for (int i=sol.size()-1;i>=0;i--) { sol[i].print_rev(sol.size()); } }
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 | #include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; #define MF 44 vector<int> fibb(MF+1); struct node { int l, r; node(int a,int b): l(a), r(b) { } void print_rev(int n) { if (l == -1) cout << l; else cout << (n-l+1); cout << ' '; if (r == -1) cout << r; else cout << (n-r+1); cout << '\n'; } }; void fill_fib() { fibb[1] = 1; fibb[2] = 1; for (int k=3;k<=MF;k++) { fibb[k] = fibb[k-1] + fibb[k-2]; //cout << k << " " << fibb[k] << '\n'; } } stack<int> podziel_fibb(int k) { stack<int> res; int j = MF; vector<int> t; while (k > 0) { while (fibb[j] > k) j--; k -= fibb[j]; //cout << fibb[j] << " (" << j << ") "; t.push_back(j); } //cout << '\n'; for(int i=t.size()-1;i>=0;i--) res.push(t[i]); return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; if (n == 1) { cout << "2\n2 -1\n-1 -1\n"; return 0; } fill_fib(); stack<int> podzial = podziel_fibb(n); int mfb = podzial.top(); //cout << "mfb=" << mfb << "\n"; vector<node> sol; sol.push_back(node(-1,-1)); sol.push_back(node(1,-1)); int z = 3; while(z <= mfb) { sol.push_back(node(z-1,z-2)); z++; } int k = mfb; while(podzial.size() > 1) { int a = podzial.top(); podzial.pop(); int b = podzial.top(); podzial.pop(); k++; podzial.push(k); node q(a,b); sol.push_back(q); } node q(podzial.top(),-1); sol.push_back(q); cout << sol.size() << '\n'; for (int i=sol.size()-1;i>=0;i--) { sol[i].print_rev(sol.size()); } } |