#include <iostream> using namespace std; int getBitCount(int k) { int count = 0; while (k) { count += k & 1; k >>= 1; } return count; } int edge[100][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int k; cin >> k; if (k == 1) { cout << 2 << endl; cout << "2 -1" << endl; cout << "-1 -1" << endl; return 0; } int m = 1; int n = 0; int lg = 0; while (2 * m <= k) { m *= 2; n += 2; lg++; } int bits = getBitCount(k); n += bits; int nn = n; edge[nn][0] = -1; edge[nn][1] = -1; for (int i = 0; i < lg; i++) { nn--; edge[nn][0] = nn + 1; edge[nn][1] = -1; nn--; edge[nn][0] = nn + 1; edge[nn][1] = nn + 2; } k -= m; int target = nn + 2; while (k > 0) { m /= 2; if (k & m) { nn--; edge[nn][0] = nn + 1; edge[nn][1] = target; k -= m; } target += 2; } cout << n << endl; for (int i = 1; i <= n; i++) { cout << edge[i][0] << " " << edge[i][1] << endl; } 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 | #include <iostream> using namespace std; int getBitCount(int k) { int count = 0; while (k) { count += k & 1; k >>= 1; } return count; } int edge[100][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int k; cin >> k; if (k == 1) { cout << 2 << endl; cout << "2 -1" << endl; cout << "-1 -1" << endl; return 0; } int m = 1; int n = 0; int lg = 0; while (2 * m <= k) { m *= 2; n += 2; lg++; } int bits = getBitCount(k); n += bits; int nn = n; edge[nn][0] = -1; edge[nn][1] = -1; for (int i = 0; i < lg; i++) { nn--; edge[nn][0] = nn + 1; edge[nn][1] = -1; nn--; edge[nn][0] = nn + 1; edge[nn][1] = nn + 2; } k -= m; int target = nn + 2; while (k > 0) { m /= 2; if (k & m) { nn--; edge[nn][0] = nn + 1; edge[nn][1] = target; k -= m; } target += 2; } cout << n << endl; for (int i = 1; i <= n; i++) { cout << edge[i][0] << " " << edge[i][1] << endl; } return 0; } |