#include #include #include #include #include #include using namespace std; constexpr int N = 45; constexpr size_t Xmax = 50; long long A[N], B[N]; #ifdef DEBUG constexpr int timelimit = 9500; #else constexpr int timelimit = 950; #endif 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, ostream &out = cout) { out << ans.size() << '\n'; for (const auto &[a, b] : ans) out << 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()); } struct State { long long a[N], b[N]; State() { copy(begin(A), end(A), begin(a)); copy(begin(B), end(B), begin(b)); } State(const State &st) { copy(begin(st.a), end(st.a), begin(a)); copy(begin(st.b), end(st.b), begin(b)); } void apply(pair x) { apply(x.first, x.second); } void apply(int i, int j) { const long long x = (a[i] + a[j]) / 2; const long long y = (b[i] + b[j]) / 2; a[i] = a[j] = x; b[i] = b[j] = y; } int get_score() const { constexpr long long target = (long long)5e17; const long long diff = max(abs(target - a[0]), abs(target - b[0])); return int(floor(2'000'000 - 100'000 * log10(diff + 1))); } }; int calc_score(const State &initial_state, const vector> &ans) { State st(initial_state); for (const auto &[p, q] : ans) { st.apply(p, q); } return st.get_score(); } 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 = 0; i < Xmax - N + 1; ++i) ans.emplace_back(1, 2); for (int i = 1; i < N; ++i) ans.emplace_back(0, i); int score = calc_score(ans); vector> best_ans = ans; auto best_score = score; mt19937 mt; int iter = 0; const auto accept = [&](int diff) { if (diff >= 0) { return true; } else { const double start_temp = 50000; const double end_temp = 10; const double progress = double(timer.get_elapsed_time()) / timelimit; const double f = progress * 10 - floor(progress * 10); const double temp = start_temp + f * (end_temp - start_temp); const double prob = exp(diff / temp); return bernoulli_distribution(prob)(mt); } }; while (timer.get_elapsed_time() < timelimit) { if (mt() % 100 == 0) { const size_t i = mt() % 6; const int p = mt() % N; const int q = mt() % N; if (p == q) continue; iter++; const auto old = ans[i]; ans[i] = {p, q}; const auto tmp_score = calc_score(ans); if (accept(tmp_score - score)) { score = tmp_score; } else { ans[i] = old; } } else { const size_t i = mt() % (ans.size() - 6) + 6; const size_t j = mt() % (ans.size() - 6) + 6; if (i == j) continue; iter++; swap(ans[i], ans[j]); const auto 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; write_ans(best_ans); calc_score(best_ans, true); }