#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 U[59], BestU[59]; long long V[59], BestV[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 <= 50; i++) { long long avgA = (LA[U[i]] + LA[V[i]]) / 2LL; long long avgB = (LB[U[i]] + LB[V[i]]) / 2LL; LA[U[i]] = avgA; LA[V[i]] = avgA; LB[U[i]] = avgB; LB[V[i]] = avgB; } 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. 焼きなまし法の初期値を決める (50 手で固定) for (int i = 1; i <= 50; i++) { while (true) { U[i] = rand() % N + 1; V[i] = rand() % N + 1; if (U[i] < V[i]) break; } } // Step 3. 焼きなまし法 (0.85 秒) long long CurrentScore = GetScore(); long long BestScore = CurrentScore; int StartTime = clock(); while (clock() - StartTime <= 85 * CLOCKS_PER_SEC / 100) { int idx = rand() % 50 + 1; int u, v; while (true) { u = rand() % N + 1; v = rand() % N + 1; if (u < v) break; } int moto_u = U[idx]; // 不採用のときのために元々の U[idx] も記録 int moto_v = V[idx]; // 不採用のときのために元々の V[idx] も記録 // 変更をする U[idx] = u; V[idx] = v; // スコアを計算 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 <= 50; i++) BestU[i] = U[i]; for (int i = 1; i <= 50; i++) BestV[i] = V[i]; } CurrentScore = CandScore; } else { U[idx] = moto_u; V[idx] = moto_v; } } // Step 4. 出力 cout << 50 << endl; for (int i = 1; i <= 50; i++) cout << BestU[i] << " " << BestV[i] << endl; return 0; }