#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; // #include // using namespace atcoder; #define rep(i, n) for (int i = 0; i < (n); ++i) #define ll long long #define double float static constexpr ll INF = 2e18; const double TIME_LIMIT = 990; const long long VAL = 5e17; const int OP_SIZE = 50; const long long N = 45; long long A[N]; long long B[N]; template T abs(const T &a, const T &b) { return a T max(const T &a, const S &b) { return a T min(const T &a, const S &b) { return a template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } // vector template ostream& operator<<(ostream& os, const vector& a) { int n = (int)a.size(); os << "["; for (int i = 0; i < n-1; ++i) { os << a[i] << ", "; } if (n > 0) { os << a.back(); } os << "]"; return os; } } // namespace titan23 using namespace titan23; // Random namespace titan23 { struct Random { unsigned int _x, _y, _z, _w; Random() { _x = 123456789; _y = 362436069; _z = 521288629; _w = 88675123; } unsigned int _xor128() { unsigned int t = _x ^ (_x << 11); _x = _y; _y = _z; _z = _w; _w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8)); return _w; } double random() { return (double)(_xor128()) / 0xFFFFFFFF; } int randint(int begin, int end) { return begin + _xor128() % (end - begin + 1); } int randrange(int begin, int end) { return begin + _xor128() % (end - begin); } }; } // namespace titan23 titan23::Random myrandom; // Timer namespace titan23 { class Timer { public: Timer() : start_timepoint(std::chrono::high_resolution_clock::now()) {} void reset() { start_timepoint = std::chrono::high_resolution_clock::now(); } double elapsed() { auto end_timepoint = std::chrono::high_resolution_clock::now(); auto start = std::chrono::time_point_cast(start_timepoint).time_since_epoch().count(); auto end = std::chrono::time_point_cast(end_timepoint).time_since_epoch().count(); return (end - start) * 0.001; // ミリ秒単位で経過時間を返す } private: std::chrono::time_point start_timepoint; }; } // SA 最小化 namespace titan23 { namespace sa { titan23::Random sa_random; struct Changed { double pre_score; int type; int indx; pair uv; int indx1, indx2; Changed() {} Changed(double score) : pre_score(score) {} }; struct State { double score; vector> op; State() : score(0.0) {} void calc_score() { ll a[N], b[N]; memcpy(a, A, N * sizeof(ll)); memcpy(b, B, N * sizeof(ll)); for (const auto &[u, v]: op) { a[u] = a[v] = (a[u]+a[v])/2; b[u] = b[v] = (b[u]+b[v])/2; } score = log(max(abs(VAL-a[0]), abs(VAL-b[0]))); } double get_score() { return score; } Changed modify() { Changed changed(score); double prob = myrandom.random(); if (prob < 0.4) { changed.type = 0; int indx1 = myrandom.randrange(0, op.size()); int indx2 = myrandom.randrange(0, op.size()); swap(op[indx1], op[indx2]); changed.indx1 = indx1; changed.indx2 = indx2; } else { changed.type = 1; int indx = myrandom.randrange(0, op.size()); auto [pre_u, pre_v] = op[indx]; int v = myrandom.randrange(1, N); while (v == pre_v) v = myrandom.randrange(1, N); changed.indx = indx; changed.uv = op[indx]; pair uv = {0, v}; op[indx] = uv; } calc_score(); return changed; } void rollback(Changed &changed) { if (changed.type == 0) { swap(op[changed.indx1], op[changed.indx2]); } else if (changed.type == 1) { op[changed.indx] = changed.uv; } score = changed.pre_score; } }; // TIME_LIMIT: ms State run(const double TIME_LIMIT) { titan23::Timer sa_timer; double START_TEMP = 10; double END_TEMP = 0.1; double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT; auto make_ans_init = [&] () -> State { State state; ll a[N], b[N]; memcpy(a, A, N * sizeof(ll)); memcpy(b, B, N * sizeof(ll)); rep(op_indx, 50) { int u = myrandom.randrange(1, N); state.op.emplace_back(0, u); } state.calc_score(); return state; }; State ans = make_ans_init(); State best_ans = ans; double score = ans.get_score(); double best_score = score; int cnt = 0; while (true) { double now_time = sa_timer.elapsed(); if (now_time > TIME_LIMIT) break; ++cnt; Changed changed = ans.modify(); double new_score = ans.get_score(); double arg = score - new_score; // if (arg < 0) cerr << arg << ' ' << exp(arg/(START_TEMP-TEMP_VAL*now_time)) << endl; if (arg >= 0 || exp(arg/(START_TEMP-TEMP_VAL*now_time)) > sa_random.random()) { score = new_score; if (score < best_score) { best_score = score; cerr << best_score << endl; best_ans = ans; } } else { ans.rollback(changed); } } cerr << "cnt=" << cnt << endl; { ll a[N], b[N]; rep(i, N) { a[i] = A[i]; b[i] = B[i]; } for (auto &[u, v]: best_ans.op) { ll x = (a[u]+a[v])/2; a[u] = x; a[v] = x; ll y = (b[u]+b[v])/2; b[u] = y; b[v] = y; } ll v1 = abs(VAL - a[0]); ll v2 = abs(VAL - b[0]); ll s = 2000000 - 100000*log10(max(v1, v2)+1); cerr << "score = " << s*50 / 1e8 << endl; } return best_ans; } } } // namespace titan23 using namespace titan23; void solve() { int n_; cin >> n_; rep(i, N) cin >> A[i] >> B[i]; sa::State ans = sa::run(TIME_LIMIT); cout << ans.op.size() << endl; for (auto &[u, v]: ans.op) { cout << u+1 << ' ' << v+1 << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); solve(); return 0; }