#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> using namespace std; const int F_MAX = 50; long long int F[F_MAX]; int L[F_MAX]; int main() { long long int k; scanf("%lld", &k); F[1] = 1; F[2] = 2; for (int i = 3; i < F_MAX; ++i) F[i] = F[i-1] + F[i-2]; int id = F_MAX - 1; long long int act = k; vector<int> idki; while (act > 0) { while (F[id] > act) --id; L[id] = 1; idki.push_back(id); act -= F[id]; --id; } //for (int i = 0; i < F_MAX; ++i) { // printf("%d", L[i]); //} //printf("\n"); //printf("F[%d] = %lld\n", idki[0], F[idki[0]]); int ile = idki.size(); int n = idki[0] + 1 + ile - 1; printf("%d\n", n); for (int i = 1; i <= ile - 1; ++i) { if (i == ile - 1) { printf("%d %d\n", n - idki[i], n - idki[i-1]); //printf("F[%d] (%lld) F[%d] (%lld)\n", idki[i], F[idki[i]], idki[i-1], F[idki[i-1]]); } else { printf("%d %d\n", i + 1, n - idki[i-1]); //printf("%d F[%d] (%lld)\n", i + 1, idki[i-1], F[idki[i-1]]); } } for (int i = 1; i < idki[0]; ++i) { printf("%d %d\n", ile-1 + i+1, ile-1 + i+2); } printf("%d %d\n", ile-1 + idki[0]+1, -1); printf("%d %d\n", -1, -1); /* G[0] = empty G[1] = {0} G[2] = {0, 1} G[3] = {1, 2} G[4] = {2, 3} G[i] = {i-1, i-2} */ 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 <cstdio> #include <cstdlib> #include <algorithm> #include <vector> using namespace std; const int F_MAX = 50; long long int F[F_MAX]; int L[F_MAX]; int main() { long long int k; scanf("%lld", &k); F[1] = 1; F[2] = 2; for (int i = 3; i < F_MAX; ++i) F[i] = F[i-1] + F[i-2]; int id = F_MAX - 1; long long int act = k; vector<int> idki; while (act > 0) { while (F[id] > act) --id; L[id] = 1; idki.push_back(id); act -= F[id]; --id; } //for (int i = 0; i < F_MAX; ++i) { // printf("%d", L[i]); //} //printf("\n"); //printf("F[%d] = %lld\n", idki[0], F[idki[0]]); int ile = idki.size(); int n = idki[0] + 1 + ile - 1; printf("%d\n", n); for (int i = 1; i <= ile - 1; ++i) { if (i == ile - 1) { printf("%d %d\n", n - idki[i], n - idki[i-1]); //printf("F[%d] (%lld) F[%d] (%lld)\n", idki[i], F[idki[i]], idki[i-1], F[idki[i-1]]); } else { printf("%d %d\n", i + 1, n - idki[i-1]); //printf("%d F[%d] (%lld)\n", i + 1, idki[i-1], F[idki[i-1]]); } } for (int i = 1; i < idki[0]; ++i) { printf("%d %d\n", ile-1 + i+1, ile-1 + i+2); } printf("%d %d\n", ile-1 + idki[0]+1, -1); printf("%d %d\n", -1, -1); /* G[0] = empty G[1] = {0} G[2] = {0, 1} G[3] = {1, 2} G[4] = {2, 3} G[i] = {i-1, i-2} */ return 0; } |