#include #include #include #include #include using namespace std; const long long Target = 500000000000000000LL; long long N; long long A[59], LA[59]; long long B[59], LB[59]; long long Order[59], BestOrder[59]; // 現在のスコアを計算する関数 (操作は 50 手, i 回目の操作は U[i], V[i]) long long GetScore() { 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 = 1; i <= N - 1; i++) { long long avgC = (LA[Order[1]] + LA[Order[i + 1]]) / 2LL; long long avgD = (LB[Order[1]] + LB[Order[i + 1]]) / 2LL; LA[Order[1]] = avgC; LA[Order[i + 1]] = avgC; LB[Order[1]] = avgD; LB[Order[i + 1]] = avgD; } return max(abs(Target - LA[1]), abs(Target - LB[1])); } // ランダムな 0 以上 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; } int main() { // Step 1. 入力 cin >> N; for (int i = 1; i <= N; i++) cin >> A[i] >> B[i]; // Step 2. 焼きなまし法の初期値を決める for (int i = 1; i <= N; i++) Order[i] = i; long long CurrentScore = GetScore(); long long BestScore = CurrentScore; int StartTime = clock(); // Step 3. 焼きなまし法 (0.85 秒) while (clock() - StartTime <= 85 * CLOCKS_PER_SEC / 100) { int idx1 = rand() % (N - 1) + 2; int idx2 = rand() % (N - 1) + 2; // 変更をする swap(Order[idx1], Order[idx2]); // スコアを計算 long long CandScore = GetScore(); double Diff = log10(CurrentScore) - log10(CandScore); // 採用するか決定 [確率は exp(log10(スコアの悪化分)/0.2)] if (Randouble() < exp(Diff / 0.2)) { if (BestScore > CandScore) { BestScore = CandScore; for (int i = 1; i <= N; i++) BestOrder[i] = Order[i]; } CurrentScore = CandScore; } else { swap(Order[idx1], Order[idx2]); } } // Step 4. 答えを得る vector> Answer; for (int i = 1; i <= N - 1; i++) Answer.push_back(make_pair(BestOrder[1], BestOrder[i + 1])); // Step 5. 出力 cout << Answer.size() << endl; for (int i = 0; i < Answer.size(); i++) cout << Answer[i].first << " " << Answer[i].second << endl; return 0; }