#include<cstdio> int k; int e1[101]; int e2[101]; int n = 2; void input() { scanf("%d", &k); for (int i = 0; i < 101; i++) { e1[i] = -1; e2[i] = -1; } } void solve(int k) { if (k == 1) { e1[1] = 0; n = 2; k--; return; } else if (k == 2) { e1[1] = 0; e1[2] = 1; e2[2] = 0; n = 3; return; } // while (k > 0) { // if (k % 2 == 1) { // e1[n] = 0; // e2[n] = n - 1; // n++; // k--; // } else { // e1[n] = n - 1; // e1[n + 1] = n - 1; // e2[n + 1] = n; // n += 2; // k /= 2; // } // } if (k % 2 == 1) { solve(k - 1); e1[n] = 0; e2[n] = n - 1; n++; } else { solve(k / 2); e1[n] = n - 1; e1[n + 1] = n - 1; e2[n + 1] = n; n += 2; } } int transform(int x) { return x == -1 ? -1 : n - x; } void print() { printf("%d\n", n); for (int i = n - 1; i >= 0; i--) { printf("%d %d\n", transform(e1[i]), transform(e2[i])); } } int test(int i) { int res = 0; if (i == 0) { return 1; } if (e1[i] >= 0) { res += test(e1[i]); } if (e2[i] >= 0) { res += test(e2[i]); } return res; } int test() { return test(n - 1); } int main() { input(); solve(k); print(); // printf("%d\n", test()); 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 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 | #include<cstdio> int k; int e1[101]; int e2[101]; int n = 2; void input() { scanf("%d", &k); for (int i = 0; i < 101; i++) { e1[i] = -1; e2[i] = -1; } } void solve(int k) { if (k == 1) { e1[1] = 0; n = 2; k--; return; } else if (k == 2) { e1[1] = 0; e1[2] = 1; e2[2] = 0; n = 3; return; } // while (k > 0) { // if (k % 2 == 1) { // e1[n] = 0; // e2[n] = n - 1; // n++; // k--; // } else { // e1[n] = n - 1; // e1[n + 1] = n - 1; // e2[n + 1] = n; // n += 2; // k /= 2; // } // } if (k % 2 == 1) { solve(k - 1); e1[n] = 0; e2[n] = n - 1; n++; } else { solve(k / 2); e1[n] = n - 1; e1[n + 1] = n - 1; e2[n + 1] = n; n += 2; } } int transform(int x) { return x == -1 ? -1 : n - x; } void print() { printf("%d\n", n); for (int i = n - 1; i >= 0; i--) { printf("%d %d\n", transform(e1[i]), transform(e2[i])); } } int test(int i) { int res = 0; if (i == 0) { return 1; } if (e1[i] >= 0) { res += test(e1[i]); } if (e2[i] >= 0) { res += test(e2[i]); } return res; } int test() { return test(n - 1); } int main() { input(); solve(k); print(); // printf("%d\n", test()); return 0; } |