#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 111; int f[N], f1[N], f2[N]; int a[N], a1[N], a2[N]; int id[N], who[N]; int main() { int k; scanf("%d", &k); f[0] = 1; f1[0] = -1; f2[0] = -1; f[1] = 1; f1[1] = 0; f2[1] = -1; int n = 2; for (n = 2; n < 50; n++) { f[n] = f[n-1] + f[n-2]; f1[n] = n-1; f2[n] = n-2; //cerr << n << " " << f[n] << "\n"; if (f[n] > k) break; } int ai = 0, j = n; a[0] = k; while (a[ai] > 0) { while (f[j] > a[ai]) j--; a1[ai] = j; a2[ai] = n+ai+1; a[ai+1] = a[ai] - f[j]; ai++; } a2[ai-1] = -1; int m = n+ai; FOR(i,n) { id[i] = m-i; who[m-i] = i; //printf("%d is fib[%d] = %d\n", m-i, i, f[i]); } FOR(i,ai) { id[n+i] = i+1; who[i+1] = n+i; //printf("%d is a[%d] = %d\n", i+1, i, a[i]); } printf("%d\n", m); FORI(i,m) { int w = who[i]; if (w < n) printf("%d %d\n", f1[w]==-1?-1:id[f1[w]], f2[w]==-1?-1:id[f2[w]]); else printf("%d %d\n", a1[w-n]==-1?-1:id[a1[w-n]], a2[w-n]==-1?-1:id[a2[w-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 66 67 68 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 111; int f[N], f1[N], f2[N]; int a[N], a1[N], a2[N]; int id[N], who[N]; int main() { int k; scanf("%d", &k); f[0] = 1; f1[0] = -1; f2[0] = -1; f[1] = 1; f1[1] = 0; f2[1] = -1; int n = 2; for (n = 2; n < 50; n++) { f[n] = f[n-1] + f[n-2]; f1[n] = n-1; f2[n] = n-2; //cerr << n << " " << f[n] << "\n"; if (f[n] > k) break; } int ai = 0, j = n; a[0] = k; while (a[ai] > 0) { while (f[j] > a[ai]) j--; a1[ai] = j; a2[ai] = n+ai+1; a[ai+1] = a[ai] - f[j]; ai++; } a2[ai-1] = -1; int m = n+ai; FOR(i,n) { id[i] = m-i; who[m-i] = i; //printf("%d is fib[%d] = %d\n", m-i, i, f[i]); } FOR(i,ai) { id[n+i] = i+1; who[i+1] = n+i; //printf("%d is a[%d] = %d\n", i+1, i, a[i]); } printf("%d\n", m); FORI(i,m) { int w = who[i]; if (w < n) printf("%d %d\n", f1[w]==-1?-1:id[f1[w]], f2[w]==-1?-1:id[f2[w]]); else printf("%d %d\n", a1[w-n]==-1?-1:id[a1[w-n]], a2[w-n]==-1?-1:id[a2[w-n]]); } return 0; } |