Hướng dẫn giải của Mua bưởi (đề KS2 ĐH 2024)
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
Cho N đồng, tìm số quả bưởi tối đa có thể mua. Giá phụ thuộc số lượng mua: 100 quả đầu 5500đ/quả, từ quả 101 đến 500 giá 8500đ/quả, từ quả 501 đến 2000 giá 15000đ/quả, còn mua trên 2000 quả thì giá 12000đ/quả cho tất cả. Với N ≤ 10^9 cần tính khéo.
Sub 1: Vét cạn — ~O(N)~
Viết hàm cost(x) tính tiền mua x quả theo đúng quy tắc, rồi thử mọi x từ 1 đến N, giữ x lớn nhất có cost(x) ≤ N. Đúng nhưng với N lớn số lần thử quá nhiều, đạt 17/20 test, 3 test còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
// Tiền phải trả khi mua x quả bưởi (đồng)
long long cost(long long x) {
if (x <= 100) return 5500 * x;
if (x <= 500) return 550000 + 8500 * (x - 100);
if (x <= 2000) return 3950000 + 15000 * (x - 500);
return 12000 * x; // trên 2000 quả: giá 12000 cho tất cả
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N;
cin >> N;
// Vét cạn: thử mọi số quả x từ 1 đến N, x mua được nếu cost(x) <= N
long long ans = 0;
for (long long x = 1; x <= N; x++)
if (cost(x) <= N) ans = x;
cout << ans << "\n";
return 0;
}
Sub 2: Xét hai khoảng số lượng — ~O(1)~
Lưu ý quan trọng: giá không tăng đều. Mua 2000 quả tốn khoảng 26,45 triệu đồng, trong khi mua 2001 quả chỉ tốn 12000 × 2001 ≈ 24,01 triệu đồng. Vì vậy không thể chỉ tăng x cho đến khi vượt tiền.
Ta xét riêng hai trường hợp:
- Mua tối đa 2000 quả: tiền tăng theo số quả nên thử
x = 1..2000và lấyxlớn nhất thỏa mãn. - Mua trên 2000 quả: giá cố định 12000đ/quả, số quả tối đa là
N / 12000, chỉ dùng khi kết quả này lớn hơn 2000.
Đáp án là giá trị lớn hơn trong hai trường hợp. Dùng long long để tránh tràn số. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Tiền phải trả khi mua x quả bưởi (đồng)
long long cost(long long x) {
if (x <= 100) return 5500 * x;
if (x <= 500) return 550000 + 8500 * (x - 100);
if (x <= 2000) return 3950000 + 15000 * (x - 500);
return 12000 * x; // trên 2000 quả: giá 12000 cho tất cả
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N;
cin >> N;
// Lưu ý: giá không đơn điệu (mua 2001 quả có thể rẻ hơn 2000 quả),
// nên xét riêng hai trường hợp.
long long ans = 0;
// 1) Mua tối đa 2000 quả: cost tăng theo x nên lấy x lớn nhất thỏa mãn
for (long long x = 1; x <= 2000; x++)
if (cost(x) <= N) ans = x;
// 2) Mua trên 2000 quả: giá 12000/quả, lấy số quả lớn nhất = N / 12000 (nếu > 2000)
long long big = N / 12000;
if (big > 2000) ans = max(ans, big);
cout << ans << "\n";
return 0;
}
Bình luận