Hướng dẫn giải của [KS cụm QL] Câu 1: Thời gian khác biệt
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
Sau x năm trên hành tinh VT25 (tính theo VT25), Tuấn có T + x tuổi, còn mỗi con có C + K·x và H + K·x tuổi, vì mỗi năm VT25 tương ứng K năm Trái Đất. Cần tìm x nhỏ nhất để Tuấn nhỏ tuổi hơn cả hai con, với điều kiện Tuấn chưa quá 100 tuổi; nếu không có thì in 00.
Sub 1: Vét cạn theo từng năm — ~O(100)~
Thử lần lượt x = 0, 1, 2, … đến khi T + x = 100, kiểm tra điều kiện với cả hai con. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long K, T, C, H;
cin >> K >> T >> C >> H;
// Vét cạn: thử từng số năm x (tính theo hành tinh VT25), tối đa đến khi Tuấn 100 tuổi
// Sau x năm VT25: Tuấn T+x tuổi, mỗi con C+K*x và H+K*x tuổi (K năm Trái Đất = 1 năm VT25)
for (long long x = 0; T + x <= 100; x++) {
if (T + x < C + K * x && T + x < H + K * x) {
cout << x << "\n";
return 0;
}
}
// Không thỏa mãn đến khi Tuấn 100 tuổi
cout << "00\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
Điều kiện T + x < C + K·x tương đương (K − 1)·x > T − C, nên có thể giải trực tiếp: x nhỏ nhất là ⌊(T − C)/(K − 1)⌋ + 1 (khi T − C < 0 thì x = 0, khi K = 1 thì không bao giờ thỏa mãn nếu T ≥ C). Lấy max của hai mốc cho hai con rồi so với giới hạn 100 tuổi. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Số năm VT25 tối thiểu x để Tuấn nhỏ tuổi hơn con có tuổi c:
// T + x < c + K*x <=> (K-1)*x > T - c
// Trả về -1 nếu không bao giờ thỏa mãn.
long long needYears(long long K, long long T, long long c) {
long long d = T - c;
if (d < 0) return 0; // đã nhỏ tuổi hơn con ngay từ bây giờ
if (K == 1) return -1; // K = 1: khoảng cách tuổi không đổi, không bao giờ thỏa mãn
return d / (K - 1) + 1; // số nguyên nhỏ nhất x sao cho (K-1)*x > d
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long K, T, C, H;
cin >> K >> T >> C >> H;
// Cần thỏa mãn với cả hai con nên lấy năm lớn hơn trong hai mốc
long long x1 = needYears(K, T, C);
long long x2 = needYears(K, T, H);
if (x1 < 0 || x2 < 0) {
cout << "00\n";
return 0;
}
long long x = max(x1, x2);
// Tuấn chỉ được tính đến khi 100 tuổi
if (T + x > 100) cout << "00\n";
else cout << x << "\n";
return 0;
}
Bình luận