#include <bits/stdc++.h> using namespace std; int k; const int N = 109; int n = 100, fib[N], max_ind; pair<int, int> dag[N]; vector<int> find_fibsum(int num) { vector<int> fib_ind; for(int i = max_ind; i >= 1; i--) { if(num - fib[i] >= 0) { fib_ind.push_back(i); num -= fib[i]; } } return fib_ind; } void build_dag() { for(int i = 1; i <= n; i++) dag[i] = {-1, -1}; dag[n - 1] = {n, -1}; for(int i = n - 2; i >= n - max_ind; i--) { dag[i] = {i + 1, i + 2}; } int v = n - max_ind - 1; auto fib_ind = find_fibsum(k); dag[v] = {n - fib_ind[0], -1}; v--; for(int i = 1; i < fib_ind.size(); i++) { dag[v] = {n - fib_ind[i], v + 1}; v--; } dag[1] = {v + 1, -1}; } int calc_fib() { fib[1] = 1; fib[2] = 2; int i = 3; while(fib[i - 1] < 1e9) { fib[i] = fib[i - 1] + fib[i - 2]; i++; } return i - 2; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> k; max_ind = calc_fib(); build_dag(); cout << n << "\n"; for(int i = 1; i <= n; i++) { cout << dag[i].first << ' ' << dag[i].second << "\n"; } 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 | #include <bits/stdc++.h> using namespace std; int k; const int N = 109; int n = 100, fib[N], max_ind; pair<int, int> dag[N]; vector<int> find_fibsum(int num) { vector<int> fib_ind; for(int i = max_ind; i >= 1; i--) { if(num - fib[i] >= 0) { fib_ind.push_back(i); num -= fib[i]; } } return fib_ind; } void build_dag() { for(int i = 1; i <= n; i++) dag[i] = {-1, -1}; dag[n - 1] = {n, -1}; for(int i = n - 2; i >= n - max_ind; i--) { dag[i] = {i + 1, i + 2}; } int v = n - max_ind - 1; auto fib_ind = find_fibsum(k); dag[v] = {n - fib_ind[0], -1}; v--; for(int i = 1; i < fib_ind.size(); i++) { dag[v] = {n - fib_ind[i], v + 1}; v--; } dag[1] = {v + 1, -1}; } int calc_fib() { fib[1] = 1; fib[2] = 2; int i = 3; while(fib[i - 1] < 1e9) { fib[i] = fib[i - 1] + fib[i - 2]; i++; } return i - 2; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> k; max_ind = calc_fib(); build_dag(); cout << n << "\n"; for(int i = 1; i <= n; i++) { cout << dag[i].first << ' ' << dag[i].second << "\n"; } return 0; } |