Hướng dẫn giải của [200 đề thầy Đức] Bài 53: Bài thi
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
Cần tìm số bài điểm 2 ít nhất để tổng điểm của ~n~ bài đúng bằng ~k~, mỗi bài có điểm từ 2 đến 5.
Sub 1: Vét cạn các bộ đếm — ~O(n^3)~, dùng khi ~1 \le n \le 10~
Thử mọi cách chọn số bài được 2, 3, 4 điểm (số bài 5 điểm là phần còn lại). Với mỗi cách có tổng đúng ~k~ thì cập nhật số bài điểm 2 ít nhất.
Nếu chỉ nộp sub này: đúng 97/99 test.
Sub 2: Công thức — ~O(1)~, dùng khi mọi trường hợp còn lại
Nếu có ~x~ bài điểm 2 thì ~n-x~ bài còn lại có tổng ~k-2x~, nằm trong khoảng ~[3(n-x), 5(n-x)]~. Vế trái cho ~x \ge 3n-k~, nên đáp án nhỏ nhất là ~\max(0, 3n-k)~. Đề bảo đảm có cách đạt tổng ~k~ nên không cần kiểm tra thêm.
Nếu chỉ nộp sub này: đúng 99/99 test.
Chương trình hoàn chỉnh
Chương trình đọc ~n, k~. Nếu ~1 \le n \le 10~ thì gọi sub1, ngược lại gọi sub2. Đề không có subtask. Một test trong dữ liệu có ~n=0~, ngoài ràng buộc ~1 \le n \le 50~; công thức vẫn cho 0 nên vẫn đúng toàn bộ test.
#include <bits/stdc++.h>
using namespace std;
int n, k; // n: so bai thi, k: tong diem can dat (moi bai tu 2 den 5)
// Sub 1: vet can. Thu moi bo (c2, c3, c4), c5 = n - c2 - c3 - c4.
// Neu tong diem = k thi cap nhat so bai diem 2 it nhat. O(n^3), dung khi n <= 10.
void sub1() {
int best = -1;
for (int c2 = 0; c2 <= n; c2++)
for (int c3 = 0; c2 + c3 <= n; c3++)
for (int c4 = 0; c2 + c3 + c4 <= n; c4++) {
int c5 = n - c2 - c3 - c4;
if (2 * c2 + 3 * c3 + 4 * c4 + 5 * c5 == k)
if (best == -1 || c2 < best) best = c2;
}
cout << best << "\n";
}
// Sub 2: cong thuc. Gia su x bai diem 2, con n - x bai co diem tu 3 den 5.
// Can 3(n-x) <= k-2x (tuc x >= 3n - k) va k-2x <= 5(n-x) (tuc x <= (5n-k)/3).
// Dap an nho nhat la x = max(0, 3n - k). O(1).
void sub2() {
cout << max(0, 3 * n - k) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
if (n >= 1 && n <= 10) sub1();
else sub2();
return 0;
}
Bình luận