#include // clang-format off using namespace std; using ll=long long; #define debug1(a) { cerr<<#a<<":"< double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS); } } // namespace marathon const int OPLIMIT = 50; const int N = 45; const ll F17 = 500000000000000000ll; 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); } double evaluate2(card_t x, card_t dest) { double da = abs(x.a - dest.a); double db = abs(x.b - dest.b); return max(da, db) * 100 + min(da, db); } void rec(vector &ops, vector &used, pair> &best_result, card_t used_total, card_t target, int lastind, int maxops, vector &now_cards) { if (ops.size() >= 1) { auto new_zero = avgfunc(used_total, now_cards[lastind]); 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 (used[j]) continue; used[j] = true; ops.push_back(j); card_t nxt_used_total = (used_total.a <= 0) ? now_cards[j] : avgfunc(now_cards[j], used_total); rec(ops, used, best_result, nxt_used_total, target, lastind, maxops, now_cards); ops.pop_back(); used[j] = false; } } void do_op(int i, int j, vector &now_cards, vector> &result) { card_t avg_ = avgfunc(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; } } namespace BeamSearch { using FORWARD_OP = pair; using BACKWARD_OP = tuple; struct node_t { int id; int parent_id; int first_child_id; int next_sibling_id; int depth; bool leaf; FORWARD_OP fwd; BACKWARD_OP bwd; double score; double realscore; }; bool operator<(const node_t &lhs, const node_t &rhs) { return lhs.score < rhs.score; } node_t node_store[10000000]; int _node_store_size = 0; int use_node_id() { _node_store_size++; return _node_store_size - 1; } void add_node_store(node_t &node) { node_store[node.id] = node; } struct board_t { bitset used; vector cards; ll a; ll b; }; class BeamSearch { public: board_t boardsrc; BeamSearch(board_t &board) { boardsrc = board; } void add_new_leafs(vector &new_leafs, int beamwidth) { // 見つけた頂点のうちスコアが高いものを木に追加 if (new_leafs.size() > beamwidth) { sort(new_leafs.rbegin(), new_leafs.rend()); new_leafs.resize(beamwidth); } unordered_map lastchild_map; for (auto leaf_ : new_leafs) { leaf_.id = use_node_id(); add_node_store(leaf_); auto &leaf = node_store[leaf_.id]; leaf.next_sibling_id = -1; auto &parent = node_store[leaf_.parent_id]; if (parent.first_child_id < 0) { parent.first_child_id = leaf.id; lastchild_map[parent.id] = leaf.id; } else { int lc = lastchild_map[parent.id]; node_store[lc].next_sibling_id = leaf.id; lastchild_map[parent.id] = leaf.id; } } } void to_child(node_t &parent, node_t &child, board_t &board) { // 親から子に移動するときのboardの変化を適用 int depth = child.fwd.first; int cardid = child.fwd.second; board.used[cardid] = true; board.a += board.cards[cardid].a / (2ll << depth); board.b += board.cards[cardid].b / (2ll << depth); } void to_parent(node_t &child, node_t &parent, board_t &board) { // 子から親に移動するときのboardの変化を適用 int cardid; ll pa, pb; tie(cardid, pa, pb) = child.bwd; board.used[cardid] = false; board.a = pa; board.b = pb; } double evaluate_score(node_t &node, board_t &board) { // スコア計算 int depth = node.fwd.first; // int cardid = node.fwd.second; ll a = board.a + F17 / (2ll << depth); ll b = board.b + F17 / (2ll << depth); return -evaluate({a, b}); } double evaluate_realscore(node_t &node, board_t &board) { // 実スコア計算 (不要な場合もある) int depth = node.fwd.first; int cardid = node.fwd.second; ll a = board.a + board.cards[cardid].a / (2ll << depth); ll b = board.b + board.cards[cardid].b / (2ll << depth); return -evaluate({a, b}); } void set_forward_backward_ops(node_t &child, node_t &parent, board_t &board, int cardid) { // 親から子、子から親に移動するときの操作をセット child.fwd = {child.depth, cardid}; child.bwd = {cardid, board.a, board.b}; } node_t make_child(node_t &parent, board_t &board, int op) { node_t child; { child.id = 1e9; child.parent_id = parent.id; child.first_child_id = -1; child.next_sibling_id = -1; child.depth = parent.depth + 1; child.leaf = true; } set_forward_backward_ops(child, parent, board, op); to_child(parent, child, board); child.score = evaluate_score(child, board); child.realscore = evaluate_realscore(child, board); to_parent(child, parent, board); return child; } void generate_new_leafs(int parent_id, board_t &board, vector &new_leafs) { // 子を生成し、 評価して新しい葉の候補として追加 auto &parent = node_store[parent_id]; for (int op = 0; op < N; op++) { if (board.used[op]) continue; if (board.a >= F17 + 10000) continue; if (board.b >= F17 + 10000) continue; node_t child = make_child(parent, board, op); new_leafs.push_back(child); } } void bs_rec(int node_id, board_t &board, vector &new_leafs) { node_t &curnode = node_store[node_id]; int before_new_leafs_cnt = new_leafs.size(); if (curnode.leaf) { // 子を生成して新しい葉の候補として追加。この頂点はもう葉でなくなる generate_new_leafs(node_id, board, new_leafs); node_store[node_id].leaf = false; } else { // 子を順にたどる if (curnode.first_child_id >= 0) { auto child = node_store[curnode.first_child_id]; while (true) { to_child(curnode, child, board); bs_rec(child.id, board, new_leafs); to_parent(child, curnode, board); if (child.next_sibling_id < 0) break; child = node_store[child.next_sibling_id]; } } } int after_new_leafs_cnt = new_leafs.size(); if (before_new_leafs_cnt == after_new_leafs_cnt) { node_store[node_id].first_child_id = -1; // 新しい葉候補を発見できていなければこの頂点はもう探索しなくていい } } vector beamsearch(int opnum) { node_t init_state = node_t(); { init_state.id = use_node_id(); init_state.parent_id = -1; init_state.next_sibling_id = -1; init_state.first_child_id = -1; init_state.fwd = {-1, -1}; init_state.bwd = {-1, -1, -1}; init_state.depth = 0; init_state.leaf = true; init_state.score = -1e18; init_state.realscore = -1e18; add_node_store(init_state); } int beamwidth = 4000; for (int op = 1; op <= opnum; op++) { debug2(op, _node_store_size); vector new_leafs; bs_rec(0, boardsrc, new_leafs); add_new_leafs(new_leafs, beamwidth); } { node_t bestnode; bestnode.realscore = -1e18; for (int nodeid = 0; nodeid < _node_store_size; nodeid++) { auto node = node_store[nodeid]; if (node.depth != opnum - 1) continue; // TODO if (node.realscore > bestnode.realscore) bestnode = node; } vector ops; auto node = bestnode; while (node.id > 0) { ops.push_back(node.fwd.second); node = node_store[node.parent_id]; } reverse(ops.begin(), ops.end()); return ops; } } }; } // namespace BeamSearch 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); } } debug2(evaluate(now_cards[0]), now_cards[0]); { BeamSearch::board_t board; board.a = now_cards[0].a / 2; board.b = now_cards[0].b / 2; board.used = 0; board.used[0] = 1; board.cards = now_cards; auto ops = BeamSearch::BeamSearch(board).beamsearch(44); int m = ops.size(); if (m > 0) { for (int i = m - 1; i >= 1; i--) { do_op(ops[i], ops[i - 1], now_cards, result); } do_op(0, ops[0], now_cards, result); } } debug2(evaluate(now_cards[0]), now_cards[0]); debug1(marathon::now()); 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; }