#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; constexpr int N = 45; constexpr int T = 50; constexpr double TIME_LIMIT = 0.95; constexpr ll BASE_SCORE = 500000000000000000; ll A[N]; ll B[N]; ll A_copy[N]; ll B_copy[N]; class Xorshift { public: Xorshift(uint64_t seed = 88675123) { _x = 123456789; _y = 362436069; _z = 521288629; _w = seed; for (int i = 0; i < 100; ++i) { next(); } } uint64_t next(uint64_t a, uint64_t b) { return a + (next() % (b - a + 1)); } uint64_t next() { uint64_t t = _x ^ (_x << 11); _x = _y; _y = _z; _z = _w; _w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8)); return _w; } double random_double() { return static_cast(next()) / UINT64_MAX; } double random_double(double a, double b) { return a + (b - a) * random_double(); } private: uint64_t _x, _y, _z, _w; }; class Timer { public: Timer() { begin(); _duration = 0.0; } void begin() { _start_at = chrono::system_clock::now(); } double get_time() { chrono::system_clock::time_point end_at = chrono::system_clock::now(); _duration = chrono::duration_cast(end_at - _start_at).count(); return _duration / 1000000000.0; } double progress(double time_limit) { return get_time() / time_limit; } private: chrono::system_clock::time_point _start_at; double _duration; }; Xorshift g_rng; class Solver { public: void run() { load_data(); setup(); auto res = sa(); /* cout << N << endl; for (int i = 0; i < N; ++i) { cout << A[i] << " " << B[i] << endl; } */ cout << res.size() << endl; for (int i = 0; i < T; ++i) { cout << res[i].first << " " << res[i].second << endl; } } private: void load_data() { int _N; cin >> _N; for (int i = 0; i < N; ++i) { cin >> A[i] >> B[i]; } } void setup() { } vector > sa(double time_limit = TIME_LIMIT) { Timer timer; int U[T], V[T]; for (int i = 0; i < T; ++i) { int u, v; do { u = g_rng.next(0, N - 1); v = g_rng.next(0, N - 1); } while (u == v); U[i] = u; V[i] = v; } int best_U[T], best_V[T]; memcpy(best_U, U, sizeof(U)); memcpy(best_V, V, sizeof(V)); int cur_score = calc_score_full(U, V); int best_score = cur_score; double cur_time = timer.get_time(); double total_diff = 0.0; double t = 0.1; ll R = 100000000; int try_count = 0; while (cur_time < time_limit) { cur_time = timer.get_time(); double remain_time = (time_limit - cur_time) / time_limit; int score = calc_score_full(U, V); double diff_score = cur_score - score; total_diff += fabs(diff_score); if (diff_score > 0 || (g_rng.next() % R < R * exp(diff_score / (t * pow(remain_time, 2))))) { cur_score = score; if (best_score < score) { best_score = score; memcpy(best_U, U, sizeof(U)); memcpy(best_V, V, sizeof(V)); } } else { } ++try_count; double average_diff = total_diff / try_count; t = 0.25 * remain_time * average_diff; } fprintf(stderr, "try_count: %d, best_score: %d\n", try_count, best_score); vector > res; for (int i = 0; i < T; ++i) { res.emplace_back(make_pair(best_U[i] + 1, best_V[i] + 1)); } return res; } int calc_score_full(int *U, int *V) { memcpy(A_copy, A, sizeof(A)); memcpy(B_copy, B, sizeof(B)); for (int i = 0; i < N; ++i) { int u = U[i]; int v = V[i]; ll sum_a = A_copy[u] + A_copy[v]; ll sum_b = B_copy[u] + B_copy[v]; A_copy[u] = sum_a >> 1; A_copy[v] = sum_a >> 1; B_copy[u] = sum_b >> 1; B_copy[v] = sum_b >> 1; } ll diff_A = abs(BASE_SCORE - A_copy[0]); ll diff_B = abs(BASE_SCORE - B_copy[0]); ll max_diff = max(diff_A, diff_B); // Score = (int)(2000000.0 - 100000.0 * math.log10(1.0 * max(ErrorA, ErrorB) + 1.0)) int score = (int) (2000000.0 - 100000.0 * log10(1.0 * max_diff + 1.0)); return score; } }; int main() { std::cin.tie(0)->sync_with_stdio(0); Solver solver; solver.run(); return 0; }