#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<<":"< &ops, vector &used, pair> &best_result, card_t used_total, card_t used_zero, int maxops, vector &now_cards) { if (ops.size() >= 1) { auto new_zero = avg(used_total, used_zero); double e = evaluate(new_zero); if (e < best_result.first) { best_result = {e, ops}; } } if (ops.size() >= maxops) { return; } for (int j = 0; j < N; j++) { if (j == 0) continue; if (used[j]) continue; used[j] = true; ops.push_back(j); card_t nxt_used_total = (used_total.a <= 0) ? now_cards[j] : avg(now_cards[j], used_total); rec(ops, used, best_result, nxt_used_total, used_zero, maxops, now_cards); ops.pop_back(); used[j] = false; } } void rec2(vector &ops, vector &used, pair> &best_result, card_t used_total, card_t used_zero, int maxops, vector &work_cards) { if (ops.size() >= 1 && ops.back() != 0) { auto new_zero = avg(work_cards[ops.back()], work_cards[0]); double e = evaluate(new_zero); if (e < best_result.first) { best_result = {e, ops}; } } if (ops.size() >= maxops) { return; } for (int j = 0; j < N; j++) { if (ops.size() == 0) { ops.push_back(j); rec2(ops, used, best_result, work_cards[j], used_zero, maxops, work_cards); ops.pop_back(); } else { int pj = ops.back(); if (j == pj) continue; card_t old_pre = work_cards[pj]; card_t old_now = work_cards[j]; card_t avg_ = avg(work_cards[j], work_cards[pj]); work_cards[pj] = avg_; work_cards[j] = avg_; ops.push_back(j); rec2(ops, used, best_result, used_total, used_zero, maxops, work_cards); ops.pop_back(); work_cards[j] = old_now; work_cards[pj] = old_pre; } } } void do_op(int i, int j, vector &now_cards, vector> &result) { card_t avg_ = avg(now_cards[i], now_cards[j]); now_cards[i] = avg_; now_cards[j] = avg_; 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 solve() { vector now_cards(N); for (int i = 0; i < N; i++) { now_cards[i] = INIT_AB[i]; } vector> result; while (result.size() <= OPLIMIT) { card_t init_0 = now_cards[0]; vector ops; vector used(N); pair> best_result = {evaluate(now_cards[0]) * 0.999, {}}; int maxop = min(4, OPLIMIT - 1 - int(result.size())); auto work_cards = now_cards; rec(ops, used, best_result, {0, 0}, init_0, maxop, work_cards); if (best_result.second.size()) { for (int j = 0; j < int(best_result.second.size()) - 1; j++) { do_op(best_result.second[j], best_result.second[j + 1], now_cards, result); } do_op(best_result.second.back(), 0, now_cards, result); debug2(best_result.first, now_cards[0]); } else { break; } } while (result.size() <= OPLIMIT) { card_t init_0 = now_cards[0]; vector ops; vector used(N); pair> best_result = {evaluate(now_cards[0]) * 0.999, {}}; int maxop = min(4, OPLIMIT - 1 - int(result.size())); rec2(ops, used, best_result, {0, 0}, init_0, maxop, now_cards); if (best_result.second.size()) { for (int j = 0; j < int(best_result.second.size()) - 1; j++) { do_op(best_result.second[j], best_result.second[j + 1], now_cards, result); } do_op(best_result.second.back(), 0, now_cards, result); debug2(best_result.first, now_cards[0]); } else { break; } } output(result); } int main() { 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; }