#include #include #include #include #include #include using namespace std; constexpr int N = 45; long long A[N], B[N]; constexpr int timelimit = 950; class Timer { chrono::system_clock::time_point start_time = chrono::system_clock::now(); public: Timer() {} long long get_elapsed_time() { auto diff = chrono::system_clock::now() - start_time; return chrono::duration_cast(diff).count(); } } timer; void write_ans(const vector> &ans) { cout << ans.size() << '\n'; for (const auto &[a, b] : ans) cout << a + 1 << ' ' << b + 1 << '\n'; } int calc_score(const vector> &ans, bool print_result = false) { long long a[N], b[N]; copy(begin(A), end(A), begin(a)); copy(begin(B), end(B), begin(b)); for (const auto &[i, j] : ans) { long long x = (a[i] + a[j]) / 2; long long y = (b[i] + b[j]) / 2; a[i] = a[j] = x; b[i] = b[j] = y; } if (print_result) for (int i = 0; i < N; ++i) cerr << a[i] << ' ' << b[i] << '\n'; constexpr long long target = (long long)5e17; const long long diff = max(abs(target - a[0]), abs(target - b[0])); return diff > 0 ? int(floor(2'000'000 - 100'000 * log10(diff + 1))) : 2'000'050 - int(ans.size()); } int main() { { int n; cin >> n; assert(n == N); } for (int i = 0; i < N; ++i) cin >> A[i] >> B[i]; vector> ans; for (int i = 1; i < N; ++i) ans.emplace_back(0, i); int score = calc_score(ans); vector> best_ans = ans; int best_score = score; mt19937 mt; int iter = 0; const auto accept = [&](int diff) { if (diff >= 0) { return true; } else { const double start_temp = 10000; const double end_temp = 10000; const double progress = double(timer.get_elapsed_time()) / timelimit; const double temp = start_temp + progress * (end_temp - start_temp); const double prob = exp(diff / temp); return bernoulli_distribution(prob)(mt); } }; while (timer.get_elapsed_time() < timelimit) { const size_t i = mt() % ans.size(); const size_t j = mt() % ans.size(); if (i == j) continue; iter++; swap(ans[i], ans[j]); const int tmp_score = calc_score(ans); if (accept(tmp_score - score)) { score = tmp_score; } else { swap(ans[i], ans[j]); } if (best_score < score) { cerr << iter << " " << score << '\n'; best_score = score; best_ans = ans; } if (iter % 100000 == 0) cerr << ' ' << iter << ' ' << score << endl; } cerr << "score = " << best_score << endl; calc_score(ans, true); write_ans(best_ans); }