Hướng dẫn giải của [2026-2027] Đề minh họa THPT Phú Thọ - Câu 1
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
Hai nhóm A (chỉ ngồi hàng 1), B (chỉ ngồi hàng 2) và nhóm C (ngồi hàng nào cũng được) cần xếp vào hai hàng m ghế. Với mỗi bộ (m, a, b, c), tìm số người nhiều nhất có thể được xếp chỗ.
Sub 1: Xếp từng người — ~O(a + b + c) mỗi truy vấn~
Xếp lần lượt từng người: nhóm A vào ghế trống hàng 1, nhóm B vào ghế trống hàng 2, rồi nhóm C vào bất kỳ ghế trống nào còn lại. Dừng khi hết ghế hoặc hết người. Đúng nhưng chậm khi số người lớn.
Kết quả chấm: 9/20 (SUB ok 9/20, TLE 11, WA 0)
#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); }
int t;
cin >> t;
while (t--) {
long long m, a, b, c;
cin >> m >> a >> b >> c;
long long r1 = m, r2 = m, dem = 0; // so ghe trong hang 1, hang 2
// Nhom A: chi ngoi hang 1
for (long long i = 0; i < a && r1 > 0; i++) { r1--; dem++; }
// Nhom B: chi ngoi hang 2
for (long long i = 0; i < b && r2 > 0; i++) { r2--; dem++; }
// Nhom C: ngoi o ghe trong bat ky
for (long long i = 0; i < c && r1 + r2 > 0; i++) {
if (r1 > 0) r1--; else r2--;
dem++;
}
cout << dem << "\n";
}
return 0;
}
Sub 2: Công thức — ~O(1) mỗi truy vấn~
Nhóm A ngồi được min(a, m) người, nhóm B ngồi được min(b, m) người. Số ghế còn trống là 2m - (chỗ A) - (chỗ B), nhóm C ngồi được min(c, số ghế trống này). Tổng là đáp số. Dùng long long vì 2m và các giá trị có thể lên tới khoảng 2·10^8.
Kết quả chấm: 20/20 (PASS 20/20)
#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); }
int t;
cin >> t;
while (t--) {
long long m, a, b, c;
cin >> m >> a >> b >> c;
// So nguoi nhom A, B ngoi duoc tren hang tuong ung (khong vuot qua m)
long long x1 = min(a, m), x2 = min(b, m);
// So ghe con trong sau khi xep A, B; nhom C ngoi vao cac ghe nay
long long conTrong = 2 * m - x1 - x2;
cout << x1 + x2 + min(c, conTrong) << "\n";
}
return 0;
}
Bình luận