Hướng dẫn giải của Đua robot (đề Hà Nội 2021)
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
Hai robot chuyển động thẳng đều: vị trí robot 1 là S1 + V1·t, robot 2 là S2 + V2·t. Hai robot gặp nhau khi hai vị trí bằng nhau, tức là t = (S2 − S1) / (V1 − V2). Kết quả cần in là phần nguyên của t, hoặc −1 nếu không bao giờ gặp (mẫu bằng 0, hoặc t âm vì hai robot đang đi xa nhau).
Sub 1: Thử từng thời điểm nguyên — ~O(|S2 − S1|)~
Duyệt t = 0, 1, 2, ... và tính khoảng cách có dấu d(t) giữa hai robot. Nếu d(t) = 0 thì gặp đúng tại t. Nếu d(t) đổi dấu so với d(0) thì hai robot đã vượt qua nhau giữa hai thời điểm t − 1 và t, nên phần nguyên là t − 1.
Kết quả chấm: đạt 5/25 test, 20 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DRB.INP", "r")) {
freopen("DRB.INP", "r", stdin);
freopen("DRB.OUT", "w", stdout);
}
long long s1, v1, s2, v2;
cin >> s1 >> v1 >> s2 >> v2;
// Vét cạn: xét từng thời điểm nguyên t = 0, 1, 2, ...
// d(t) = vị trí robot 1 - vị trí robot 2; hai robot gặp khi d(t) = 0
long long d0 = s1 - s2;
for (long long t = 0; t <= 2000000000LL; t++) {
long long d = s1 + v1 * t - (s2 + v2 * t);
if (d == 0) { // gặp đúng tại thời điểm nguyên t
cout << t << "\n";
return 0;
}
if ((d > 0) != (d0 > 0)) { // đã vượt qua nhau giữa thời điểm t-1 và t
cout << t - 1 << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}
Sub 2: Công thức tính trực tiếp — ~O(1)~
Tính t = (S2 − S1) / (V1 − V2) bằng phép chia số nguyên trên trị tuyệt đối, sau khi kiểm tra dấu. Không dùng số thực vì với giá trị đến 10^9 phép chia số thực có thể làm tròn sai phần nguyên.
Bẫy cần chú ý: V1 = V2 thì không bao giờ gặp (vì S1 ≠ S2); dấu của tử và mẫu khác nhau nghĩa là t < 0 nên in −1.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DRB.INP", "r")) {
freopen("DRB.INP", "r", stdin);
freopen("DRB.OUT", "w", stdout);
}
long long s1, v1, s2, v2;
cin >> s1 >> v1 >> s2 >> v2;
// Thời gian gặp nhau: S1 + V1*t = S2 + V2*t => t = (S2 - S1) / (V1 - V2)
long long tu = s2 - s1, mau = v1 - v2;
// Không gặp nhau khi mẫu bằng 0 hoặc t < 0 (cùng dấu thì t > 0)
if (mau == 0 || ((tu > 0) != (mau > 0))) {
cout << -1 << "\n";
return 0;
}
// Phần nguyên của t (cả tử và mẫu đều dương sau khi lấy trị tuyệt đối)
cout << llabs(tu) / llabs(mau) << "\n";
return 0;
}
Bình luận