Hướng dẫn giải của [2526 KS1 THCS] Bài 2: Nhảy xa
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Mô phỏng đúng quy định: 8 vận động viên chia thành 4 trận (S1–S2, S3–S4, S5–S6, S7–S8). Trong mỗi trận, người có cú nhảy xa hơn thắng; nếu bằng nhau thì người có số hiệu nhỏ hơn thắng. Sau đó chọn người thắng có cú nhảy lớn nhất (giải đặc biệt) và người thua có cú nhảy lớn nhất (giải an ủi), đều lấy số hiệu nhỏ hơn khi bằng nhau.
Bài chỉ có 8 số cố định nên không có cách vét cạn khác đáng kể; lời giải chỉ gồm một bước mô phỏng trực tiếp, nên viết 1 sub (đạt 9/9 test).
Sub 1: Mô phỏng trực tiếp — ~O(1)~
Xét lần lượt 4 cặp trận, ghi nhận người thắng và người thua, rồi duyệt từng nhóm để tìm cú nhảy lớn nhất. Đạt 9/9 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// d[i] là độ dài cú nhảy của S_i (i = 1..8)
int d[9];
for (int i = 1; i <= 8; i++) cin >> d[i];
// 4 trận: S1-S2, S3-S4, S5-S6, S7-S8
vector<int> win, lose;
for (int a = 1; a <= 7; a += 2) {
int b = a + 1;
// Cú nhảy xa hơn thắng; bằng nhau thì số hiệu nhỏ hơn (a) thắng
if (d[a] >= d[b]) { win.push_back(a); lose.push_back(b); }
else { win.push_back(b); lose.push_back(a); }
}
// Giải đặc biệt: người thắng có cú nhảy lớn nhất, bằng nhau chọn số hiệu nhỏ hơn
int best = win[0];
for (int x : win)
if (d[x] > d[best] || (d[x] == d[best] && x < best)) best = x;
// Giải an ủi: người thua có cú nhảy lớn nhất, bằng nhau chọn số hiệu nhỏ hơn
int worst = lose[0];
for (int x : lose)
if (d[x] > d[worst] || (d[x] == d[worst] && x < worst)) worst = x;
cout << "S" << best << "\n";
cout << "S" << worst << "\n";
return 0;
}
Bình luận