#include #include #include #include #include #include using namespace std; long long calc_score(const vector>& op, const vector& init_A, const vector& init_B, int N) { vector A = init_A, B = init_B; for (auto& p : op) { int u = p.first - 1; int v = p.second - 1; long long a = A[u], b = A[v]; A[u] = A[v] = (a + b) / 2; long long c = B[u], d = B[v]; B[u] = B[v] = (c + d) / 2; } long long V1 = abs(5e17 - A[0]); long long V2 = abs(5e17 - B[0]); long long V = -V1/2 - V2/2; return V; // long long V = max(V1, V2); // if (V == 0) { // return 2000050 - op.size(); // } else { // return floor(2000000.0 - 100000.0 * log10(V + 1)); // } } long long calc_true_score(const vector>& op, const vector& init_A, const vector& init_B, int N) { vector A = init_A, B = init_B; for (auto& p : op) { int u = p.first - 1; int v = p.second - 1; long long a = A[u], b = A[v]; A[u] = A[v] = (a + b) / 2; long long c = B[u], d = B[v]; B[u] = B[v] = (c + d) / 2; } long long V1 = abs(5e17 - A[0]); long long V2 = abs(5e17 - B[0]); long long V = max(V1, V2); if (V == 0) { return 2000050 - op.size(); } else { return floor(2000000.0 - 100000.0 * log10(V + 1)); } } int main() { srand(time(nullptr)); int N; cin >> N; vector init_A(N), init_B(N); for (int i = 0; i < N; ++i) { cin >> init_A[i] >> init_B[i]; } // 初期化 int X = 50; vector> op; vector A = init_A, B = init_B; while (op.size() < X / 2) { int min_idx_A = min_element(A.begin(), A.end()) - A.begin(); int max_idx_A = max_element(A.begin(), A.end()) - A.begin(); if (min_idx_A == max_idx_A) break; op.push_back({min_idx_A + 1, max_idx_A + 1}); long long new_value_A = (A[min_idx_A] + A[max_idx_A]) / 2; A[min_idx_A] = A[max_idx_A] = new_value_A; } // Bに対する操作 while (op.size() < X) { int min_idx_B = min_element(B.begin(), B.end()) - B.begin(); int max_idx_B = max_element(B.begin(), B.end()) - B.begin(); if (min_idx_B == max_idx_B) break; op.push_back({min_idx_B + 1, max_idx_B + 1}); long long new_value_B = (B[min_idx_B] + B[max_idx_B]) / 2; B[min_idx_B] = B[max_idx_B] = new_value_B; } // ランダムな操作を追加 while (op.size() < X) { int u = rand() % N + 1; int v = rand() % N + 1; if (u != v) { op.push_back({u, v}); } } long long score = calc_score(op, init_A, init_B, N); double start_temp = 2000.0; double end_temp = 10.0; double time_limit = 0.90; clock_t start_time = clock(); while (true) { double now_time = double(clock() - start_time) / CLOCKS_PER_SEC; if (now_time > time_limit) { break; } double temp = start_temp + (end_temp - start_temp) * now_time / time_limit; double r = double(rand()) / RAND_MAX; double diff_threshold = temp * log(r+1e-7); vector> new_op = op; int idx = rand() % op.size(); if (rand() % 2 == 0) { int u = rand() % (N-1) + 1; int v = rand() % (N-u) + u + 1; new_op[idx] = {u, v}; } else { int idx2 = rand() % op.size(); swap(new_op[idx], new_op[idx2]); } long long new_score = calc_score(new_op, init_A, init_B, N); if (new_score - score > diff_threshold) { op = move(new_op); score = new_score; } } cout << op.size() << endl; for (auto& p : op) { cout << p.first << " " << p.second << endl; } // cout << "Score: " << calc_true_score(op, init_A, init_B, N) << endl; return 0; }