#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; #include using namespace atcoder; #define ALL(a) (a).begin(), (a).end() #define FOR(i, start, end) for (int i = start; i < (int)(end); ++i) #define RFOR(i, rstart, rend) for (int i = rstart; i >= (int)(rend); --i) #define REP(i, end) FOR(i, 0, end) using ll = long long; using ull = unsigned long long; using pii = pair; using pll = pair; constexpr ll LINF = 1LL << 60; constexpr int INF = 1 << 30; template using PQ = priority_queue, greater>; templatevoid chmax(T &a, const T &b) { if (avoid chmin(T &a, const T &b) { if (b> 19)) ^ (t ^ (t >> 8)); } // [a, b) の int 乱数を生成 int irand(int a, int b){ return a + (xor128() % (b - a)); } // [0.0, 1.0) の double 乱数を生成 double drand(){ return xor128() / 4294967296.0; // UINT_MAX+1 = 4294967296 } // [a, b) の double 乱数を生成 inline double drand(double a, double b){ return a + drand() * (b - a); } }; struct Timekeeper{ Timekeeper(const int64_t &t) : start_time(std::chrono::high_resolution_clock::now()),time_threshold(t) {} bool is_timeout(){ auto end_time = std::chrono::high_resolution_clock::now(); return std::chrono::duration_cast(end_time - start_time).count() >= time_threshold; } private: std::chrono::high_resolution_clock::time_point start_time; int64_t time_threshold; }; constexpr int N = 45; constexpr int M = 50; constexpr ll G = 5e17; int n; Xorshift rnd; vector A(N),B(N); vector ans; struct State{ vector a,b; double score=-1; pii first_action={-1,-1}; State() {} State(const vector &_a, const vector &_b) : a(_a), b(_b) { calc_score(); } void calc_score(){ ll v = max(abs(a[0]-G), abs(b[0]-G)+1); score = log(v); } void action(int i, int j){ ll na = (a[i]+a[j])/2; ll nb = (b[i]+b[j])/2; a[i] = na; b[i] = nb; a[j] = na; b[j] = nb; calc_score(); } }; using StatePtr = shared_ptr; bool operator<(const StatePtr &a, const StatePtr &b){ return a->score > b->score; } pii chokudaiSearchAction( const State &state, const int beam_width, const int beam_depth, const int64_t time_threshold ){ auto timekeeper = Timekeeper(time_threshold); auto beam = vector>(beam_depth+1); beam[0].push(make_shared(state)); while(true){ REP(t,beam_depth){ auto &now_beam = beam[t]; auto &next_beam = beam[t+1]; REP(i,beam_width){ if(now_beam.empty()) break; State now_state = *now_beam.top(); now_beam.pop(); REP(i,n)FOR(j,i+1,n){ if(now_state.a[i] == now_state.a[j] && now_state.b[i] == now_state.b[j]) continue; State next_state = now_state; next_state.action(i,j); if(t==0){ next_state.first_action = {i,j}; } next_beam.push(make_shared(next_state)); } } } if(timekeeper.is_timeout()) break; } RFOR(t,beam_depth,0){ if(!beam[t].empty()){ return beam[t].top()->first_action; } } return {-1,-1}; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; REP(i,n) cin >> A[i] >> B[i]; State state(A,B); double best_score = state.score; vector tmp_ans; REP(t,M){ auto [i,j] = chokudaiSearchAction(state, 5, M-t, 15); state.action(i,j); tmp_ans.push_back({i,j}); if(state.score < best_score){ best_score = state.score; ans = tmp_ans; } } cout << ans.size() << endl; for (auto [a, b] : ans) cout << a+1 << " " << b+1 << endl; return 0; }