#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; // #include // using namespace atcoder; #define rep(i, n) for (int i = 0; i < (n); ++i) #define ll long long static constexpr ll INF = 2e18; const double TIME_LIMIT = 996; const long long VAL = 5e17; const int N = 45; long long A[N]; long long B[N]; template T abs(const T &a, const S &b) { return a T max(const T &a, const S &b) { return a T min(const T &a, const S &b) { return a> 19)) ^ (t ^ (t >> 8)); return _w; } public: Random() : _x(123456789), _y(362436069), _z(521288629), _w(88675123) {} double random() { return (double)(_xor128()) / 0xFFFFFFFF; } int randint(const int end) { return (((unsigned long long)_xor128() * (end+1)) >> 32); } int randint(const int begin, const int end) { return begin + (((unsigned long long)_xor128() * (end-begin+1)) >> 32); } int randrange(const int end) { return (((unsigned long long)_xor128() * end) >> 32); } int randrange(const int begin, const int end) { return begin + (((unsigned long long)_xor128() * (end-begin)) >> 32); } }; } // namespace titan23 titan23::Random myrandom; // Timer namespace titan23 { class Timer { public: Timer() : start_timepoint(std::chrono::high_resolution_clock::now()) {} void reset() { start_timepoint = std::chrono::high_resolution_clock::now(); } double elapsed() { auto end_timepoint = std::chrono::high_resolution_clock::now(); auto start = std::chrono::time_point_cast(start_timepoint).time_since_epoch().count(); auto end = std::chrono::time_point_cast(end_timepoint).time_since_epoch().count(); return (end - start) * 0.001; // ミリ秒単位で経過時間を返す } private: std::chrono::time_point start_timepoint; }; } // SA 最小化 double START_TEMP; double END_TEMP; namespace titan23 { namespace sa { titan23::Random sa_random; using Changed = pair; struct State { double score; vector op; State() : score(0.0) {} void calc_score() { ll a[N], b[N]; memcpy(a, A, N * sizeof(ll)); memcpy(b, B, N * sizeof(ll)); for (const int &v: op) { a[0] = (a[0]+a[v])/2; b[0] = (b[0]+b[v])/2; } score = log(max(abs(VAL-a[0]), abs(VAL-b[0]))); } double get_score() const { return score; } Changed modify() { double prob = myrandom.random(); int indx1 = myrandom.randrange(op.size()); int indx2 = myrandom.randrange(op.size()); swap(op[indx1], op[indx2]); calc_score(); return {indx1, indx2}; } void rollback(Changed &changed) { swap(op[changed.first], op[changed.second]); } }; // TIME_LIMIT: ms State run(const double TIME_LIMIT) { titan23::Timer sa_timer; // const double START_TEMP = 1; // const double END_TEMP = 0.1; const double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT; auto make_ans_init = [&] () -> State { State state; for (int u = 1; u < N; ++u) { state.op.emplace_back(u); } state.calc_score(); return state; }; State ans = make_ans_init(); State best_ans = ans; double score = ans.get_score(); double best_score = score; int cnt = 0; while (true) { double now_time = sa_timer.elapsed(); if (now_time > TIME_LIMIT) break; ++cnt; Changed changed = ans.modify(); double new_score = ans.get_score(); double arg = score - new_score; if (arg >= 0 || exp(arg/(START_TEMP-TEMP_VAL*now_time)) > sa_random.random()) { score = new_score; if (score < best_score) { best_score = score; best_ans = ans; } } else { ans.rollback(changed); } } cerr << "cnt=" << cnt << endl; { ll a[N], b[N]; rep(i, N) { a[i] = A[i]; b[i] = B[i]; } for (const int &v: best_ans.op) { ll x = (a[0]+a[v])/2; a[0] = x; a[v] = x; ll y = (b[0]+b[v])/2; b[0] = y; b[v] = y; } ll v1 = abs(VAL - a[0]); ll v2 = abs(VAL - b[0]); ll s = 2000000 - 100000*log10(max(v1, v2)+1); cerr << "score = " << s*50 / 1e8 << endl; } return best_ans; } } } // namespace titan23 using namespace titan23; void solve() { int n_; cin >> n_; rep(i, N) cin >> A[i] >> B[i]; sa::State ans = sa::run(TIME_LIMIT); cout << ans.op.size() << endl; for (const int &v: ans.op) { cout << 1 << ' ' << v+1 << endl; } } int main(int argc, char *argv[]) { ios::sync_with_stdio(false); cin.tie(0); // 2.5644564925732642, 'k': 0.000578604277039025 START_TEMP = 2.5644564925732642; END_TEMP = START_TEMP * 0.000578604277039025; // START_TEMP = stod(argv[1]); // END_TEMP = stod(argv[2]); solve(); return 0; }