#include <bits/stdc++.h> using namespace std; const int MAXN = 105; vector<int> edges[MAXN]; int names[MAXN], rev_names[MAXN]; int N = 0; pair<int,int> gen(int n) { if (n == 1) { edges[N+1].push_back(N+2); N += 2; return make_pair(N-1, N); } if (n % 2 == 0) { pair<int,int> ab = gen(n / 2); edges[ab.second].push_back(N+1); edges[ab.second].push_back(N+2); edges[N+1].push_back(N+2); N += 2; return make_pair(ab.first, N); } else { pair<int,int> ab = gen(n - 1); edges[N+1].push_back(ab.first); edges[N+1].push_back(ab.second); N++; return make_pair(N, ab.second); } } int main() { int n; cin >> n; pair<int,int> ab = gen(n); for (int i = 1; i <= N; i++) names[i] = i; while (true) { random_shuffle(names + 1, names + N + 1); if (names[ab.first] != 1) continue; if (names[ab.second] != N) continue; break; } for (int i = 1; i <= N; i++) rev_names[names[i]] = i; cout << N << "\n"; for (int i = 1; i <= N; i++) { int u = rev_names[i]; if (edges[u].size() >= 1) cout << names[edges[u][0]]; else cout << "-1"; cout << " "; if (edges[u].size() >= 2) cout << names[edges[u][1]]; else cout << "-1"; cout << "\n"; assert(edges[u].size() <= 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 | #include <bits/stdc++.h> using namespace std; const int MAXN = 105; vector<int> edges[MAXN]; int names[MAXN], rev_names[MAXN]; int N = 0; pair<int,int> gen(int n) { if (n == 1) { edges[N+1].push_back(N+2); N += 2; return make_pair(N-1, N); } if (n % 2 == 0) { pair<int,int> ab = gen(n / 2); edges[ab.second].push_back(N+1); edges[ab.second].push_back(N+2); edges[N+1].push_back(N+2); N += 2; return make_pair(ab.first, N); } else { pair<int,int> ab = gen(n - 1); edges[N+1].push_back(ab.first); edges[N+1].push_back(ab.second); N++; return make_pair(N, ab.second); } } int main() { int n; cin >> n; pair<int,int> ab = gen(n); for (int i = 1; i <= N; i++) names[i] = i; while (true) { random_shuffle(names + 1, names + N + 1); if (names[ab.first] != 1) continue; if (names[ab.second] != N) continue; break; } for (int i = 1; i <= N; i++) rev_names[names[i]] = i; cout << N << "\n"; for (int i = 1; i <= N; i++) { int u = rev_names[i]; if (edges[u].size() >= 1) cout << names[edges[u][0]]; else cout << "-1"; cout << " "; if (edges[u].size() >= 2) cout << names[edges[u][1]]; else cout << "-1"; cout << "\n"; assert(edges[u].size() <= 2); } return 0; } |