Hướng dẫn giải của Hai con thỏ (Đề HSG Quảng Ninh 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
Sau t giây, con thỏ trắng ở vị trí x + a·t và con thỏ xám ở vị trí y - b·t. Hai con gặp nhau khi x + a·t = y - b·t, tức t·(a + b) = y - x. Vì x < y nên y - x > 0, và đáp án là t = (y - x) / (a + b) nếu chia hết, ngược lại in -1. Các số có thể lên tới 10^15 nên dùng long long.
Sub 1: Mô phỏng từng giây — ~O((y - x) / (a + b))~
Cho t = 1, 2, ... và kiểm tra vị trí hai con thỏ. Nếu bằng nhau thì in t. Nếu vị trí thỏ trắng đã vượt qua thỏ xám (p > q) thì không bao giờ gặp nhau nữa nên in -1. Đúng nhưng số bước có thể lên tới khoảng 10^15 / 2 nên chỉ đủ nhanh với các test nhỏ (khoảng 10^7).
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("rab.inp", "r")) { freopen("rab.inp", "r", stdin); freopen("rab.out", "w", stdout); }
long long x, y, a, b;
cin >> x >> y >> a >> b;
// Vet can: mo phong tung giay t = 1, 2, ...
// Vi tri con trang: x + a*t, con xam: y - b*t
for (long long t = 1;; t++) {
long long p = x + a * t; // vi tri con thỏ trang sau t giay
long long q = y - b * t; // vi tri con thỏ xam sau t giay
if (p == q) {
cout << t << "\n";
return 0;
}
// Khoang cach da doi chieu (p vuot q) thi khong bao gio gap nhau nua
if (p > q) break;
}
cout << -1 << "\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
Từ t·(a + b) = y - x suy ra chỉ cần kiểm tra (y - x) có chia hết cho (a + b) hay không. Nếu có thì đáp án là thương, không thì in -1. Lưu ý a + b ≤ 2·10^15 nên vẫn nằm trong long long, không bị tràn.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("rab.inp", "r")) { freopen("rab.inp", "r", stdin); freopen("rab.out", "w", stdout); }
long long x, y, a, b;
cin >> x >> y >> a >> b;
// Sau t giay: x + a*t = y - b*t => t*(a+b) = y - x
// Moi giay khoang cach giam (a+b), nen can (y - x) chia het cho (a + b) va t > 0
long long d = y - x; // d > 0 vi x < y
long long s = a + b; // toi da 2*10^15, khong tran long long
if (d % s != 0) {
cout << -1 << "\n";
return 0;
}
cout << d / s << "\n";
return 0;
}
Bình luận