#include <bits/stdc++.h> #define FOR(i, a, b) for(int i = a; i<b; ++i) #define FR(a, b) for(int i = a; i>=b;--i) #define _fastio cin.tie(0); ios_base::sync_with_stdio(0) #define pb push_back #define mp make_pair #define INF 1e18 using namespace std; typedef long long ll; typedef double db; typedef unsigned long long ull; typedef pair<int, int> iPair; const int MAX = 3e5 + 2; const int M = 1e9 +7; int fib[45], k; iPair rozw[101]; vector<int> res; int main() { //_fastio; fib[1] = fib[2] = 1; FOR(i, 3, 45) { fib[i] = fib[i-1]+fib[i-2]; // cout<<fib[i]<<" "; } FOR(i, 1, 101) rozw[i] = {-1, -1}; cin>>k; int id = 44; while(k > 0) { while(fib[id] <= k) { res.pb(id); k -= fib[id]; } id--; } int cur = res[0]+1; FOR(i, 1, res[0]) rozw[i].first = i+1; FOR(i, 1, res[0]-1) rozw[i].second = i+2; FOR(i, 1, res.size()) { rozw[res[i]].second = cur; rozw[cur].first = res[0]; if(res[i]+2 == res[0]) { rozw[cur].second = cur+1; rozw[cur+1].first = res[0]; cur++; } else rozw[cur].second = res[i]+2; cur++; } FOR(i, 1, cur) { if(rozw[i].first == cur-1) rozw[i].first = res[0]; else if(rozw[i].first == res[0]) rozw[i].first = cur-1; if(rozw[i].second == cur-1) rozw[i].second = res[0]; else if(rozw[i].second == res[0]) rozw[i].second = cur-1; } swap(rozw[cur-1], rozw[res[0]]); cout<<cur-1<<"\n"; FOR(i, 1, cur) cout<<rozw[i].first<<" "<<rozw[i].second<<"\n"; }
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 | #include <bits/stdc++.h> #define FOR(i, a, b) for(int i = a; i<b; ++i) #define FR(a, b) for(int i = a; i>=b;--i) #define _fastio cin.tie(0); ios_base::sync_with_stdio(0) #define pb push_back #define mp make_pair #define INF 1e18 using namespace std; typedef long long ll; typedef double db; typedef unsigned long long ull; typedef pair<int, int> iPair; const int MAX = 3e5 + 2; const int M = 1e9 +7; int fib[45], k; iPair rozw[101]; vector<int> res; int main() { //_fastio; fib[1] = fib[2] = 1; FOR(i, 3, 45) { fib[i] = fib[i-1]+fib[i-2]; // cout<<fib[i]<<" "; } FOR(i, 1, 101) rozw[i] = {-1, -1}; cin>>k; int id = 44; while(k > 0) { while(fib[id] <= k) { res.pb(id); k -= fib[id]; } id--; } int cur = res[0]+1; FOR(i, 1, res[0]) rozw[i].first = i+1; FOR(i, 1, res[0]-1) rozw[i].second = i+2; FOR(i, 1, res.size()) { rozw[res[i]].second = cur; rozw[cur].first = res[0]; if(res[i]+2 == res[0]) { rozw[cur].second = cur+1; rozw[cur+1].first = res[0]; cur++; } else rozw[cur].second = res[i]+2; cur++; } FOR(i, 1, cur) { if(rozw[i].first == cur-1) rozw[i].first = res[0]; else if(rozw[i].first == res[0]) rozw[i].first = cur-1; if(rozw[i].second == cur-1) rozw[i].second = res[0]; else if(rozw[i].second == res[0]) rozw[i].second = cur-1; } swap(rozw[cur-1], rozw[res[0]]); cout<<cur-1<<"\n"; FOR(i, 1, cur) cout<<rozw[i].first<<" "<<rozw[i].second<<"\n"; } |