#include #include #include #include #include using namespace std; const long long MaxVal = 1000000000000000000LL; const long long MinVal = 100000000000000000LL; const long long Target = 500000000000000000LL; long long N; long long A[59], LA[59]; long long B[59], LB[59]; long long FinalScore = MaxVal; vector FinalOrder; // ========================================================================================================== 基本関数 long long GetScore(vector& Order) { long long TotalScore1 = (A[1] >> (N - 1)); long long TotalScore2 = (B[1] >> (N - 1)); for (int i = 0; i < N - 1; i++) TotalScore1 += (A[Order[i]] >> (N - 1 - i)); for (int i = 0; i < N - 1; i++) TotalScore2 += (B[Order[i]] >> (N - 1 - i)); return max(abs(Target - TotalScore1), abs(Target - TotalScore2)); } pair GetActual(vector& Order) { for (int i = 1; i <= N; i++) LA[i] = A[i]; for (int i = 1; i <= N; i++) LB[i] = B[i]; for (int i = 0; i < Order.size(); i++) { long long avgA = (LA[1] + LA[Order[i]]) / 2LL; long long avgB = (LB[1] + LB[Order[i]]) / 2LL; LA[1] = avgA; LA[Order[i]] = avgA; LB[1] = avgB; LB[Order[i]] = avgB; } long long gosa1 = max(abs(Target - LA[1]), abs(Target - LB[1])); long long gosa2 = max(abs(Target - LA[1] + (A[Order[0]] >> N) - (A[Order[1]] >> N)), abs(Target - LB[1] + (B[Order[0]] >> N) - (B[Order[1]] >> N))); if (gosa1 > gosa2) return make_pair(gosa2, 2); return make_pair(gosa1, 1); } long double Randouble() { double s = 0.0, t = 1.0; for (int i = 0; i < 3; i++) { t /= 1024.0; s += 1.0 * (rand() % 1024) * t; } return s; } // ========================================================================================================== 序盤・中盤探索 vector GetBestOrder() { vector Order(N - 1, 0); vector BestOrder(N - 1, 0); for (int i = 0; i < N - 1; i++) Order[i] = i + 2; // 準備 long long CurrentScore = GetScore(Order); long long BestScore = CurrentScore; int StartTime = clock(); // 焼きなまし法開始 while (clock() - StartTime <= 35 * CLOCKS_PER_SEC / 100) { int idx1 = rand() % (N - 1); int idx2 = rand() % (N - 1); swap(Order[idx1], Order[idx2]); long long CandScore = GetScore(Order); double Diff = log10(CurrentScore) - log10(CandScore); if (Randouble() < exp(Diff / 0.17)) { if (BestScore > CandScore) { BestScore = CandScore; BestOrder = Order; } CurrentScore = CandScore; } else { swap(Order[idx1], Order[idx2]); } } return BestOrder; } // ========================================================================================================== 終盤探索 vector CurrentOrder; int StartTime; int NumLoops; int FinalTie = 0; void dfs(int mask, long long CurrentA, long long CurrentB, vector& Cand, vector& PostOrder) { if ((NumLoops & 1023) == 0) { if (clock() - StartTime > 85 * CLOCKS_PER_SEC / 100) return; } NumLoops += 1; if (mask == (1 << Cand.size()) - 1) { if (max(abs(Target - CurrentA), abs(Target - CurrentB)) > FinalScore + 100LL) return; vector Final; for (int i = CurrentOrder.size() - 1; i >= 0; i--) Final.push_back(CurrentOrder[i]); for (int i = 0; i < PostOrder.size(); i++) Final.push_back(PostOrder[i]); pair Score = GetActual(Final); if (FinalScore > Score.first) { FinalScore = Score.first; FinalTie = Score.second; FinalOrder = Final; } return; } // 枝刈り探索 int dep = PostOrder.size() + CurrentOrder.size() + 1; long long Border1 = 12LL * (MaxVal >> dep) / 10LL; long long Border2 = 10000LL; for (int i = 0; i < Cand.size(); i++) { if ((mask >> i) & 1) continue; long long NextA = CurrentA + (A[Cand[i]] >> dep); long long NextB = CurrentB + (B[Cand[i]] >> dep); if (NextA < Target - Border1) continue; if (NextB < Target - Border1) continue; if (NextA > Target + Border2) continue; if (NextB > Target + Border2) continue; CurrentOrder.push_back(Cand[i]); dfs(mask + (1 << i), NextA, NextB, Cand, PostOrder); CurrentOrder.pop_back(); } } int main() { // Step 1. 入力 cin >> N; for (int i = 1; i <= N; i++) cin >> A[i] >> B[i]; // Step 2. 焼きなまし法 StartTime = clock(); vector BestOrder = GetBestOrder(); // Step 3. 終盤探索 for (int depth = 0; depth <= 18; depth++) { long long SumA = (A[1] >> (N - 1)); long long SumB = (B[1] >> (N - 1)); for (int i = depth; i < N - 1; i++) SumA += (A[BestOrder[i]] >> (N - 1 - i)); for (int i = depth; i < N - 1; i++) SumB += (B[BestOrder[i]] >> (N - 1 - i)); vector Vec1; vector Vec2; for (int i = 0; i < depth; i++) Vec1.push_back(BestOrder[i]); for (int i = depth; i < N - 1; i++) Vec2.push_back(BestOrder[i]); dfs(0, SumA, SumB, Vec1, Vec2); // cout << "# " << depth << " " << FinalScore << " " << NumLoops << endl; if (clock() - StartTime > 85 * CLOCKS_PER_SEC / 100) break; } // Step 4. 出力 vector> Answer; if (FinalTie == 2) Answer.push_back(make_pair(FinalOrder[0], FinalOrder[1])); for (int i = 0; i < FinalOrder.size(); i++) Answer.push_back(make_pair(1, FinalOrder[i])); cout << Answer.size() << endl; for (pair ans : Answer) cout << ans.first << " " << ans.second << endl; return 0; }