Hướng dẫn giải của [2526 VTT THPT KS1] Bài 2: Mua bánh
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
Tèo chỉ đi trong giờ ra chơi hoặc sau khi hết học, và phải về trước tiết tiếp theo, nên đoạn đi dài A phút phải nằm trọn trong một giờ ra chơi. Cần tìm số phút chờ ít nhất, hoặc in NOW nếu đi được ngay.
Sub 1: Vét cạn theo phút - ~O(T \cdot A)~ (A = B)
Thử từng X = 0, 1, 2,... xem đoạn ~[t+X, t+X+A)~ có nằm trọn trong giờ ra chơi (hoặc sau khi hết học) không. Đúng 10/10 test.
Sub 2: Duyệt các giờ ra chơi
Với mỗi giờ ra chơi ~[bs, be)~, thời điểm đi sớm nhất là ~s = max(t, bs)~; nếu ~s + A \le be~ thì là ứng viên với số phút chờ ~s - t~. Sau khi hết học cũng là một ứng viên. Nếu đáp số là 0 thì in NOW. Đúng 10/10 test.
Chương trình hoàn chỉnh
main dựng lịch 12 tiết (tiết đầu 08:00, giờ ra chơi sau tiết 3 và 9 dài B phút, các giờ khác dài A phút). Nếu A = B gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int S, A, B, H, M;
int schoolEnd; // phut ket thuc tiet 12
vector<pair<int, int>> breaks; // cac gio ra choi [bs, be) tinh bang phut tu 0h
const int TMAX = 4000;
bool freeMin[TMAX]; // freeMin[t] = phut t la gio ra choi hoac sau khi het hoc
// Sub 1: vet can theo phut. Thu X = 0,1,2,... xem doan [t0+X, t0+X+A) co nam hoan toan trong
// gio ra choi (hoac sau gio hoc) khong. Dung khi A = B (subtask 1).
void sub1() {
int t0 = H * 60 + M;
for (int X = 0; X < 1500; X++) {
bool ok = true;
for (int t = t0 + X; t < t0 + X + A && ok; t++)
if (!freeMin[t]) ok = false;
if (ok) {
if (X == 0) cout << "NOW\n";
else cout << X << "\n";
return;
}
}
}
// Sub 2: xet tung gio ra choi. Cau di bat dau luc s = max(t0, bs), phai co s + A <= be.
// Sau khi het hoc thi luon duoc di (coi nhu gio ra choi vo han).
void sub2() {
int t0 = H * 60 + M;
if (t0 >= schoolEnd) {
cout << "NOW\n";
return;
}
long long best = schoolEnd - t0; // di sau khi het hoc
for (auto& br : breaks) {
int s = max(t0, br.first);
if (s + A <= br.second) best = min<long long>(best, s - t0);
}
if (best == 0) cout << "NOW\n";
else cout << best << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> S >> A >> B >> H >> M;
// Tiet 1 bat dau 08:00, moi tiet S phut. Sau tiet 3 va tiet 9 la gio dai B phut, cac gio khac la A phut.
int t = 8 * 60;
for (int p = 1; p <= 12; p++) {
t += S;
if (p < 12) {
int len = (p == 3 || p == 9) ? B : A;
breaks.push_back({t, t + len});
t += len;
}
}
schoolEnd = t;
for (auto& br : breaks)
for (int x = br.first; x < br.second; x++) freeMin[x] = true;
for (int x = schoolEnd; x < TMAX; x++) freeMin[x] = true;
if (A == B) sub1();
else sub2();
return 0;
}
Bình luận