#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) uint64_t rand64() { static uint64_t x = 88172645463325252ULL; x = x ^ (x << 7); return x = x ^ (x >> 9); } double rand_p() { return rand64() * (1.0 / UINT64_MAX); } using namespace std::chrono; using namespace std; struct Timer { system_clock::time_point start; Timer() { reset(); } void reset() { start = system_clock::now(); } double sec_elapsed() const { return duration_cast(system_clock::now() - start).count() / 1000.0; } }; constexpr int N = 45; constexpr int M = 50; long long A[N]; long long B[N]; void input() { int tmp; std::cin >> tmp; REP(i, N) { std::cin >> A[i] >> B[i]; } } struct State { std::vector> operations; std::vector testA; std::vector testB; int old_index, old_i, old_j; State() { REP(k, M) { int i = rand64() % N; int j = rand64() % N; operations.emplace_back(i, j); } testA.resize(N); testB.resize(N); } void modify() { int index = rand64() % M; int i = rand64() % N; int j = rand64() % N; modify(index, i, j); } void modify(int index, int i, int j) { old_index = index; old_i = operations[index].first; old_j = operations[index].second; operations[index] = std::make_pair(i, j); } void rollback() { operations[old_index] = std::make_pair(old_i, old_j); } long long calc_score() { REP(i, N) { testA[i] = A[i]; testB[i] = B[i]; } for (auto &op : operations) { int i = op.first; int j = op.second; long long avgA = (testA[i] + testA[j]) / 2LL; long long avgB = (testB[i] + testB[j]) / 2LL; testA[i] = avgA; testA[j] = avgA; testB[i] = avgB; testB[j] = avgB; } long long ErrorA = abs(500000000000000000LL - testA[0]); long long ErrorB = abs(500000000000000000LL - testB[0]); long long Score = (long long)(2000000.0L - 100000.0L * log10(1.0L * max(ErrorA, ErrorB) + 1.0L)); return Score; } void print() { int invalid_count = 0; REP(i, M) { int a = operations[i].first; int b = operations[i].second; if (a == b) { invalid_count += 1; } } std::cout << M - invalid_count << std::endl; REP(i, M) { int a = operations[i].first; int b = operations[i].second; if (a != b) { std::cout << a + 1<< " " << b + 1 << std::endl; } } } }; State annealing(State cur_state, const Timer &timer, const double time_limit) { // 温度設定 const double start_temp = 1e0; const double end_temp = 1e0; double inv_temp = 1.0 / start_temp; int iter_count = 0; long long cur_score = cur_state.calc_score(); State best_state = cur_state; long long best_score = best_state.calc_score(); double start_time = timer.sec_elapsed(); double now = start_time; while (now < time_limit) { if (iter_count & 1024) { now = timer.sec_elapsed(); const double time_ratio = (now - start_time) / (time_limit - start_time); // const double temp = start_temp + (end_temp - start_temp) * time_ratio; // 線形 const double temp = start_temp * std::pow(end_temp / start_temp, time_ratio); // pow inv_temp = 1.0 / temp; } cur_state.modify(); long long new_score = cur_state.calc_score(); double prob = std::exp((new_score - cur_score) * inv_temp); if (prob > rand_p()) { cur_score = new_score; } else { cur_state.rollback(); } if (cur_score > best_score) { best_score = cur_score; best_state = cur_state; } iter_count += 1; } std::cerr << iter_count << std::endl; return best_state; } State kick(State cur_state, const Timer &timer, const double time_limit) { int iter_count = 0; long long cur_score = cur_state.calc_score(); State best_state = cur_state; long long best_score = best_state.calc_score(); double start_time = timer.sec_elapsed(); double now = start_time; while (now < time_limit) { now = timer.sec_elapsed(); bool update = false; REP(index, M) REP(i, N) REP3(j, i + 1, N) { cur_state.modify(index, i, j); long long new_score = cur_state.calc_score(); if (new_score > cur_score) { cur_score = new_score; update = true; } else { cur_state.rollback(); } } if (cur_score > best_score) { best_score = cur_score; best_state = cur_state; } if (!update) { // kickする cur_state = best_state; cur_state.modify(); cur_state.modify(); cur_score = cur_state.calc_score(); } iter_count += 1; } std::cerr << iter_count << std::endl; return best_state; } int main() { input(); Timer timer; State state; state = annealing(state, timer, 0.95); //state = kick(state, timer, 0.95); std::cerr << state.calc_score() << std::endl; state.print(); }