Hướng dẫn giải của Trò chơi (đề HSG 9 Phú Thọ 2024-2025)
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
Có n người xuất phát từ các vị trí si trên trục và đi về gốc O với tốc độ vi. Tìm người đến O đầu tiên (thời gian ti = |si| / v_i), nếu trùng thời gian thì lấy số thứ tự nhỏ hơn.
Sub 1: So sánh từng cặp — ~O(n^2)~
Với mỗi người i, kiểm tra xem có người j nào đến O sớm hơn không (hoặc cùng lúc nhưng j < i). Nếu không có thì i là đáp án. So sánh thời gian bằng nhân chéo để tránh số thực. Cách này đúng nhưng với n lên tới 10^5 thì quá chậm.
Kết quả chấm: đạt 20/20 test (SUB ok 20/20, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
// So sánh thời gian đi: người i đến O trước người j khi |s_i|/v_i < |s_j|/v_j
// Nhân chéo để tránh số thực: |s_i| * v_j < |s_j| * v_i
bool nhanhHon(long long si, long long vi, long long sj, long long vj) {
return llabs(si) * vj < llabs(sj) * vi;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> s(n), v(n);
for (auto &x : s) cin >> x;
for (auto &x : v) cin >> x;
// Vét cạn: người i là kết quả nếu không có người j nào đến O sớm hơn (hoặc cùng lúc nhưng j < i)
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = 0; j < n && ok; j++) {
if (j == i) continue;
if (nhanhHon(s[j], v[j], s[i], v[i])) ok = false;
else if (!nhanhHon(s[i], v[i], s[j], v[j]) && j < i) ok = false;
}
if (ok) {
cout << i + 1 << "\n";
return 0;
}
}
return 0;
}
Sub 2: Duyệt một lần, giữ người nhanh nhất — ~O(n)~
Duyệt từ người 1 đến n, giữ người có thời gian nhỏ nhất đến lúc đó. So sánh nghiêm ngặt, nên khi hai người bằng thời gian thì giữ người có số thứ tự nhỏ hơn. So sánh thời gian bằng |si|·vj < |sj|·vi để không dùng số thực; tích tối đa 10^12 nên dùng long long.
Kết quả chấm: đạt 20/20 test
#include <bits/stdc++.h>
using namespace std;
// Người i đến O sớm hơn người b khi |s_i|/v_i < |s_b|/v_b (nhân chéo, không dùng số thực)
bool nhanhHon(long long si, long long vi, long long sb, long long vb) {
return llabs(si) * vb < llabs(sb) * vi;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> s(n), v(n);
for (auto &x : s) cin >> x;
for (auto &x : v) cin >> x;
// Duyệt một lượt, giữ người đến sớm nhất; so sánh nghiêm ngặt nên khi bằng nhau giữ người có số thứ tự nhỏ hơn
int best = 0;
for (int i = 1; i < n; i++)
if (nhanhHon(s[i], v[i], s[best], v[best])) best = i;
cout << best + 1 << "\n";
return 0;
}
Bình luận