#include #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; int Masks[1 << 20]; vector> List[15600][1000]; // ========================================================================================================== 基本関数 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)); } long long 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 gosa = max(abs(Target - LA[1]), abs(Target - LB[1])); return gosa; } 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 <= 25 * 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; void dfs(int depth, int mask, long long CurrentA, long long CurrentB, vector& Cand, vector& PostOrder) { if ((NumLoops & 1023) == 0) { if (clock() - StartTime > 70 * CLOCKS_PER_SEC / 100) return; } NumLoops += 1; if (depth <= 5) { int idx = Masks[(1 << Cand.size()) - 1 - mask]; int Remain = max(0LL, min(999LL, (Target - CurrentA) / 2000LL)); for (tuple tup : List[idx][Remain]) { long long gosaA = abs(Target - (CurrentA + 1LL * get<1>(tup))); long long gosaB = abs(Target - (CurrentB + 1LL * get<0>(tup))); if (max(gosaA, gosaB) > FinalScore + 100LL) continue; vector Final; for (int i = 0; i < 5; i++) Final.push_back(Cand[(get<2>(tup) >> (5 * i)) & 31]); 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]); long long Score = GetActual(Final); if (FinalScore > Score) { FinalScore = Score; 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(depth - 1, 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. 終盤探索 (初期化) int IndexCount = 0; for (int i = 0; i < 20; i++) { for (int j = i + 1; j < 20; j++) { for (int k = j + 1; k < 20; k++) { for (int l = k + 1; l < 20; l++) { for (int m = l + 1; m < 20; m++) { vector Order = { i, j, k, l, m }; do { long long sumA = 0; long long sumB = 0; for (int idx = 0; idx < Order.size(); idx++) { sumA += A[BestOrder[Order[idx]]] >> (N - 1 - idx); sumB += B[BestOrder[Order[idx]]] >> (N - 1 - idx); } List[IndexCount][sumA / 2000LL].push_back(make_tuple(sumB, sumA, Order[0] + (Order[1] << 5) + (Order[2] << 10) + (Order[3] << 15) + (Order[4] << 20))); } while (next_permutation(Order.begin(), Order.end())); for (int n = 0; n < 1000; n++) { if (List[IndexCount][n].size() <= 1) continue; sort(List[IndexCount][n].begin(), List[IndexCount][n].end()); } Masks[(1 << i) + (1 << j) + (1 << k) + (1 << l) + (1 << m)] = IndexCount; IndexCount += 1; } } } } } // Step 3. 終盤探索 for (int depth = 6; 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(depth, 0, SumA, SumB, Vec1, Vec2); // printf("% 3d% 9lld% 9d% 7d\n", depth, min(99999999LL, FinalScore), NumLoops, clock() - StartTime); if (clock() - StartTime > 70 * CLOCKS_PER_SEC / 100) break; } // Step 4. 出力 vector> Answer; 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; }