#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 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 #include using namespace std; // print namespace titan23 { // pair 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(const int begin, const int end) { return begin + _xor128() % (end - begin + 1); } int randint(const int end) { return ((long long)_xor128() * (end+1)) >> 32; } int randrange(const int end) { return ((long long)_xor128() * (end)) >> 32; } int randrange(const int begin, const int end) { return begin + (((long long)_xor128() * (end - begin))>>32); } }; } // namespace titan23 titan23::Random myrandom; int u = myrandom.randint(1); int a = myrandom.randint(1); // 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 show_true_score() const { ll a[N], b[N]; rep(i, N) { a[i] = A[i]; b[i] = B[i]; } for (auto &[u, v]: 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; } 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; } ll v1 = abs(VAL - a[0]); ll v2 = abs(VAL - b[0]); score = log10(max(v1, v2)+1); } double get_score() { return score; } Changed modify() { Changed changed(score); double prob = myrandom.random(); if (op.empty() || (prob < 0.1 && op.size()+1 <= OP_SIZE)) { changed.type = 0; int indx = myrandom.randint(op.size()); int u = myrandom.randrange(N); int v = myrandom.randrange(N); while (u == v) { v = myrandom.randrange(N); } pair uv = {u, v}; op.insert(op.begin()+indx, uv); changed.indx = indx; } else if (prob < 0.15) { changed.type = 1; int indx = myrandom.randrange(op.size()); changed.indx = indx; changed.uv = op[indx]; op.erase(op.begin() + indx); } else if (prob < 0.8) { changed.type = 10; { assert(!op.empty()); int indx = myrandom.randrange(op.size()); changed.indx1 = indx; changed.uv = op[indx]; op.erase(op.begin() + indx); } { int indx = myrandom.randint(op.size()); int u = myrandom.randrange(N); int v = myrandom.randrange(N); while (u == v) { v = myrandom.randrange(N); } pair uv = {u, v}; changed.indx2 = indx; op.insert(op.begin()+indx, uv); } } else if (prob < 0.9) { changed.type = 2; int indx = myrandom.randrange(op.size()); int u = myrandom.randrange(N); int v = myrandom.randrange(N); while (u == v) { v = myrandom.randrange(N); } changed.indx = indx; changed.uv = op[indx]; pair uv = {u, v}; op[indx] = uv; } else { changed.type = 3; int indx = myrandom.randrange(op.size()); auto [pre_u, pre_v] = op[indx]; int u = pre_u, v = pre_v; if (myrandom.random() < 0.4) { u = myrandom.randrange(N); while (u == pre_u || u == pre_v) { u = myrandom.randrange(N); } } else { v = myrandom.randrange(N); while (v == pre_v || v == pre_u) { v = myrandom.randrange(N); } } changed.indx = indx; changed.uv = op[indx]; pair uv = {u, v}; op[indx] = uv; } calc_score(); return changed; } void rollback(Changed &changed) { if (changed.type == 0) { op.erase(op.begin() + changed.indx); } else if (changed.type == 1) { op.insert(op.begin() + changed.indx, changed.uv); } else if (changed.type == 2) { op[changed.indx] = changed.uv; } else if (changed.type == 3) { op[changed.indx] = changed.uv; } else if (changed.type == 10) { op.erase(op.begin() + changed.indx2); op.insert(op.begin() + changed.indx1, changed.uv); } score = changed.pre_score; } }; // TIME_LIMIT: ms State run(const double TIME_LIMIT) { titan23::Timer sa_timer; const double START_TEMP = 0.000001; const double END_TEMP = 0.00000001; const double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT; auto make_ans_init = [&] () -> State { State state; rep(_, 41) { int u = myrandom.randrange(N); int v = myrandom.randrange(N); while (u == v) v = myrandom.randrange(N); state.op.emplace_back(u, v); } state.calc_score(); return state; ll a[N], b[N]; memcpy(a, A, N * sizeof(ll)); memcpy(b, B, N * sizeof(ll)); rep(op_indx, 40) { if (op_indx == 39) { // to 0; vector delta(N, INF); ll mn = INF; for (int i = 1; i < N; ++i) { delta[i] = max(abs(VAL-(a[0]+a[i])/2), abs(VAL-(b[0]+b[i])/2)); if (delta[i] < mn) mn = delta[i]; } for (int i = 1; i < N; ++i) { if (delta[i] == mn) { state.op.emplace_back(0, i); break; } } } else { pair ans; ll best = INF; for (int i = 1; i < N; ++i) { for (int j = i+1; j < N; ++j) { ll this_s = abs(VAL - (a[0] + (a[i]+a[j])/2) / 2) + abs(VAL - (b[0] + (b[i]+b[j])/2) / 2); if (this_s < best) { best = this_s; ans = {i, j}; } } } state.op.push_back(ans); } } 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 << VAL << endl; cerr << a[0] << endl; cerr << b[0] << endl; 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; }