// [想定解答 4] // - 山登り法を行う. // - 具体的には、カードを選ぶ順番 Order[1], Order[2], ..., Order[N] に対して山登り法を適用する. // * 1 手目: カード Order[1] と Order[2] を選んで操作する // * 2 手目: カード Order[2] と Order[3] を選んで操作する // * 3 手目: カード Order[3] と Order[4] を選んで操作する // * : // * N-1 手目: カード Order[N-1] と Order[N] を選んで操作する // - 山登り法の近傍はある i, j について Order[i] と Order[j] を swap. // - 35% 程度の得点が得られる. #include #include #include #include #include using namespace std; const long long Target = 500000000000000000LL; long long N; long long A[59], C[59]; long long B[59], D[59]; long long Order[59]; long long GetScore() { for (int i = 1; i <= N; i++) C[i] = A[i]; for (int i = 1; i <= N; i++) D[i] = B[i]; for (int i = 1; i <= N - 1; i++) { long long avgC = (C[Order[i]] + C[Order[i + 1]]) / 2LL; long long avgD = (D[Order[i]] + D[Order[i + 1]]) / 2LL; C[Order[i]] = avgC; C[Order[i + 1]] = avgC; D[Order[i]] = avgD; D[Order[i + 1]] = avgD; } return max(abs(Target - C[1]), abs(Target - D[1])); } 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(); int StartTime = clock(); while (clock() - StartTime <= 85 * CLOCKS_PER_SEC / 100) { int idx1 = rand() % N + 1; int idx2 = rand() % N + 1; swap(Order[idx1], Order[idx2]); long long CandScore = GetScore(); if (CurrentScore >= CandScore) { CurrentScore = CandScore; } else { swap(Order[idx1], Order[idx2]); } } // Step 3. 答えを得る vector> Answer; for (int i = 1; i <= N - 1; i++) Answer.push_back(make_pair(Order[i], Order[i + 1])); // Step 4. 出力 cout << Answer.size() << endl; for (int i = 0; i < Answer.size(); i++) cout << Answer[i].first << " " << Answer[i].second << endl; return 0; }