#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; #define debug1(a) { cerr<<#a<<":"< T random_choice(vector &vec) { return vec[engine() % vec.size()]; } bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) { const int ANNEAL_RND = 1e8; const double ANNEAL_EPS = 1e-6; double temp = (begin_temp * (end_time - cur_time) + end_temp * (cur_time - begin_time)) / (end_time - begin_time); return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS); } } // namespace marathon const int OPLIMIT = 50; const int N = 45; const ll F17 = 500000000000000000; card_t INIT_AB[N]; double evaluate(card_t x) { double da = abs(x.a - F17); double db = abs(x.b - F17); return max(da, db) * 100 + min(da, db); } void do_op(int i, int j, vector &now_cards, vector> &result) { card_t g = avgfunc(now_cards[i], now_cards[j]); now_cards[i] = g; now_cards[j] = g; result.push_back({i, j}); } void output(vector> &result) { cout << result.size() << endl; for (auto p : result) { cout << p.first + 1 << " " << p.second + 1 << endl; } } void anneal(vector &now_cards, int opnum, vector> &result) { vector ops; for (int i = 0; i < opnum; i++) { ops.push_back(i); } card_t card_zero = {0, 0}; double old_score = 0; { for (int i = 0; i < int(ops.size()); i++) { card_zero.a += now_cards[ops[i]].a / (2ll << i); card_zero.b += now_cards[ops[i]].b / (2ll << i); } card_zero.a += now_cards[ops.back()].a / (2ll << (int(ops.size()) - 1)); card_zero.b += now_cards[ops.back()].b / (2ll << (int(ops.size()) - 1)); old_score = -evaluate(card_zero); } pair> bestops = {old_score, ops}; auto add3 = [&](int sign, int xi, int yi, int zi, int x, int y, int z) { if (sign == 1) { card_zero.a += now_cards[x].a / (2ll << xi); card_zero.b += now_cards[x].b / (2ll << xi); card_zero.a += now_cards[y].a / (2ll << yi); card_zero.b += now_cards[y].b / (2ll << yi); card_zero.a += now_cards[z].a / (2ll << zi); card_zero.b += now_cards[z].b / (2ll << zi); } else { card_zero.a -= now_cards[x].a / (2ll << xi); card_zero.b -= now_cards[x].b / (2ll << xi); card_zero.a -= now_cards[y].a / (2ll << yi); card_zero.b -= now_cards[y].b / (2ll << yi); card_zero.a -= now_cards[z].a / (2ll << zi); card_zero.b -= now_cards[z].b / (2ll << zi); } }; auto add1 = [&](int xi, int x) { card_zero.a += now_cards[x].a / (2ll << xi); card_zero.b += now_cards[x].b / (2ll << xi); }; auto sub1 = [&](int xi, int x) { card_zero.a -= now_cards[x].a / (2ll << xi); card_zero.b -= now_cards[x].b / (2ll << xi); }; double begin_temp = log(1e7) * 0.05; double end_temp = begin_temp * 0.1; double begin_time = marathon::now(); int anneal_iter = 0; int anneal_accepted = 0; vector candidate; while (marathon::now() < 900) { anneal_iter++; int xi = 0; int yi = 0; int zi = 0; while (xi == yi || yi == zi || zi == xi) { xi = marathon::randint(1, int(ops.size()) - 2); // TODO 末尾も変更 yi = marathon::randint(1, int(ops.size()) - 2); zi = marathon::randint(1, int(ops.size()) - 2); } int old_x = ops[xi]; int old_y = ops[yi]; int old_z = ops[zi]; add3(-1, xi, yi, zi, old_x, old_y, old_z); bitset used = 0; for (auto op : ops) { used[op] = 1; } used[old_x] = false; used[old_y] = false; used[old_z] = false; candidate.clear(); for (int cardid = 0; cardid < N; cardid++) { if (!used[cardid]) candidate.push_back(cardid); } tuple bestresult = {-1e50, -1, -1, -1}; { for (auto new_x : candidate) { add1(xi, new_x); for (auto new_y : candidate) { if (new_x == new_y) continue; add1(yi, new_y); for (auto new_z : candidate) { if (new_x == new_z) continue; if (new_y == new_z) continue; if (old_x == new_x && old_y == new_y && old_z == new_z) continue; add1(zi, new_z); double score = -evaluate(card_zero); if (score > get<0>(bestresult)) { bestresult = {score, new_x, new_y, new_z}; } sub1(zi, new_z); } sub1(yi, new_y); } sub1(xi, new_x); } } double new_score; int new_x, new_y, new_z; tie(new_score, new_x, new_y, new_z) = bestresult; if (marathon::anneal_accept(log(abs(old_score)), log(abs(new_score)), marathon::now(), begin_time, 900, begin_temp, end_temp)) { anneal_accepted++; // if (anneal_accepted % 1000 == 0) debug2(new_score, old_score); old_score = new_score; ops[xi] = new_x; ops[yi] = new_y; ops[zi] = new_z; add3(1, xi, yi, zi, new_x, new_y, new_z); if (bestops.first < new_score) { bestops = {new_score, ops}; } } else { add3(1, xi, yi, zi, old_x, old_y, old_z); } } debug2(anneal_iter, anneal_accepted); for (int i = int(bestops.second.size() - 1); i > 0; i--) { do_op(bestops.second[i], bestops.second[i - 1], now_cards, result); } } void solve() { vector now_cards(N); for (int i = 0; i < N; i++) { now_cards[i] = INIT_AB[i]; } vector> result; { tuple bestresult = {-1e50, -1, -1, -1}; for (int x = 1; x < N; x++) { for (int y = 1; y < N; y++) { if (x == y) continue; for (int z = 1; z < N; z++) { if (x == z) continue; if (y == z) continue; card_t c0 = now_cards[0]; card_t cx = now_cards[x]; card_t cy = now_cards[y]; card_t cz = now_cards[z]; card_t nxt_c0 = {c0.a / 2 + cx.a / 4 + cy.a / 8 + cz.a / 8, c0.b / 2 + cx.b / 4 + cy.b / 8 + cz.b / 8}; double score = -evaluate(nxt_c0); bestresult = max(bestresult, {score, x, y, z}); } } } { double score; int x, y, z; tie(score, x, y, z) = bestresult; do_op(z, y, now_cards, result); do_op(y, x, now_cards, result); do_op(x, 0, now_cards, result); } } debug3(evaluate(now_cards[0]), now_cards[0].a, now_cards[0].b); anneal(now_cards, 45, result); debug3(evaluate(now_cards[0]), now_cards[0].a, now_cards[0].b); output(result); } int main() { marathon::marathon_init(); int n; cin >> n; for (int i = 0; i < n; i++) { ll a, b; cin >> a >> b; INIT_AB[i] = card_t{a, b}; } solve(); return 0; }