Hướng dẫn giải của Tải bài giảng (đề 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
Gọi T0 là thời gian đợi, video dài Z giây, phát X MB mỗi giây, mạng tải Y MB mỗi giây (Y < X). Đến giây k của video, An đã tải được Y·(T0 + k) MB, và cần ít nhất X·k MB để phát liên tục. Vì Y < X nên vế trái tăng chậm hơn vế phải, do đó chỉ cần kiểm tra tại giây cuối k = Z: Y·(T0 + Z) ≥ X·Z, tức là T0 ≥ Z·(X − Y) / Y. Đáp số là số nguyên nhỏ nhất thỏa mãn, tức là làm tròn lên.
Ví dụ: X = 10, Y = 3, Z = 2 cho Z(X−Y)/Y = 14/3 ≈ 4,67, làm tròn lên được 5.
Sub 1: Thử từng T0 và kiểm tra mọi giây — ~O(Z \cdot T0)~
Thử T0 = 1, 2, ... ; với mỗi T0 kiểm tra mọi giây k từ 1 đến Z xem Y·(T0 + k) ≥ X·k có đúng không. Lấy T0 đầu tiên thỏa mãn. Cách này không dựa vào nhận xét đơn điệu nên dễ kiểm tra, nhưng T0 có thể rất lớn khi X và Y gần nhau.
Kết quả chấm: đạt 16/20 test, 4 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("TBG.INP", "r")) {
freopen("TBG.INP", "r", stdin);
freopen("TBG.OUT", "w", stdout);
}
long long x, y, z;
cin >> x >> y >> z;
// Vét cạn: thử lần lượt T0 = 1, 2, ...; với mỗi T0 kiểm tra mọi giây k = 1..Z
// điều kiện: đến giây k của video, đã tải được Y*(T0+k) MB, không ít hơn X*k MB cần phát
for (long long t0 = 1;; t0++) {
bool ok = true;
for (long long k = 1; k <= z && ok; k++)
if (y * (t0 + k) < x * k) ok = false;
if (ok) {
cout << t0 << "\n";
return 0;
}
}
return 0;
}
Sub 2: Công thức làm tròn lên — ~O(1)~
Tính tử số Z·(X − Y) (tối đa khoảng 10^10, cần long long), rồi làm tròn lên khi chia cho Y bằng công thức (tu + Y − 1) / Y.
Bẫy: không dùng số thực để làm tròn lên vì dễ sai với số lớn; chỉ dùng số nguyê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("TBG.INP", "r")) {
freopen("TBG.INP", "r", stdin);
freopen("TBG.OUT", "w", stdout);
}
long long x, y, z;
cin >> x >> y >> z;
// Điều kiện Y*(T0+Z) >= X*Z (vế trái - vế phải giảm dần theo thời gian vì Y < X)
// nên T0 >= Z*(X-Y)/Y, lấy số nguyên nhỏ nhất: làm tròn lên
long long tu = z * (x - y); // tối đa 10^10 nên dùng long long
long long t0 = (tu + y - 1) / y; // làm tròn lên của tu / y
cout << t0 << "\n";
return 0;
}
Bình luận