Quà chợ nổi (Đề tự luyện HSG Tin 9 – Bài 4)
Đề bài
Quà chợ nổi. Có $N$ món quà, món $i$ giá $c_i$ nghìn đồng, độ vui $v_i$; mỗi món mua tối đa một lần. Khuyến mãi: mua từ 3 món trở lên thì món rẻ nhất trong các món đã mua được tặng (chỉ một món). Thầy Sơn có $B$ nghìn đồng, mua trong một lần. Tìm tổng độ vui lớn nhất (không mua gì thì bằng $0$).
Dữ liệu vào: dòng 1 là $N, B$ $(1 \le N \le 2000,\ 0 \le B \le 10^4)$; $N$ dòng sau là $c_i, v_i$ $(1 \le c_i \le 2\cdot10^4,\ 1 \le v_i \le 10^9)$.
Kết quả: tổng độ vui lớn nhất.
- Subtask 1 (20%): $N \le 15$.
- Subtask 2 (30%): $N \le 100$.
- Subtask 3 (50%): không ràng buộc thêm.
6 29
16 19
7 6
18 9
12 19
9 5
11 1957Mua món $1, 4, 6$ (giá $16, 12, 11$): món $6$ rẻ nhất được tặng, trả $16 + 12 = 28 \le 29$, độ vui $19 \cdot 3 = 57$.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Quà chợ nổiLời mở đầu
Bỏ khuyến mãi đi thì đây chính là bài cái túi 0/1 quen thuộc: chọn các món có tổng giá $\le B$ sao cho tổng độ vui lớn nhất. Khuyến mãi làm bài "khó chịu" ở hai chỗ:
- Món được tặng phụ thuộc vào cả giỏ hàng. Món rẻ nhất là món nào thì phải chọn xong mới biết. Thêm một món rẻ hơn vào giỏ là món được tặng "đổi chủ".
- Phải đủ 3 món. Mua 1–2 món thì trả đủ tiền, nên lời giải phải đếm số món đã chọn (ít nhất tới mốc 3).
Chìa khóa: nếu ta xét các món theo thứ tự giá tăng dần, thì món đầu tiên được bỏ vào giỏ chính là món rẻ nhất của giỏ! Vậy chỉ cần quyết định ngay từ món đầu tiên: "giỏ này sẽ dùng khuyến mãi" — món đầu tiên miễn phí, và sau đó bắt buộc phải mua thêm ít nhất 2 món nữa.
Hình 1. Các món của ví dụ xếp theo giá. Giỏ tốt nhất $\{11, 12, 16\}$: món $11$ được chọn đầu tiên nên chắc chắn là món rẻ nhất, được tặng.
Cách 1Thử mọi tập con – O(2^N · N) · 20%
Với $N \le 15$ chỉ có $2^{15} = 32768$ cách chọn giỏ. Mỗi giỏ biểu diễn bằng một số nhị phân $s$ (bit $i$ bằng $1$ nghĩa là mua món $i$). Với mỗi giỏ, tính tổng tiền, tổng độ vui, số món và giá rẻ nhất; nếu có từ 3 món thì trừ giá rẻ nhất khỏi tổng tiền. Giỏ nào tổng tiền $\le B$ thì cập nhật đáp án.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, B;
cin >> n >> B;
vector<ll> c(n), v(n);
for (int i = 0; i < n; i++) cin >> c[i] >> v[i];
ll best = 0; // khong mua gi: do vui 0
for (int s = 1; s < (1 << n); s++) { // thu moi tap mon qua
ll tien = 0, vui = 0, re = LLONG_MAX;
int dem = 0;
for (int i = 0; i < n; i++)
if (s >> i & 1) {
tien += c[i]; vui += v[i];
re = min(re, c[i]); // gia mon re nhat
dem++;
}
if (dem >= 3) tien -= re; // khuyen mai: tang mon re nhat
if (tien <= B) best = max(best, vui);
}
cout << best << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); B = int(data[1])
c = [int(x) for x in data[2:2 * n + 2:2]]
v = [int(x) for x in data[3:2 * n + 3:2]]
best = 0 # khong mua gi: do vui 0
for s in range(1, 1 << n): # thu moi tap mon qua
tien = vui = dem = 0
re = None
for i in range(n):
if s >> i & 1:
tien += c[i]; vui += v[i]; dem += 1
if re is None or c[i] < re:
re = c[i] # gia mon re nhat
if dem >= 3:
tien -= re # khuyen mai: tang mon re nhat
if tien <= B and vui > best:
best = vui
print(best)
main()Cách 2Thử từng món được tặng – O(N² · B) · 50%
Có hai loại giỏ:
- Giỏ 1–2 món (trả đủ tiền): thử mọi món và mọi cặp món, $O(N^2)$.
- Giỏ từ 3 món: đoán trước món được tặng. Sắp xếp các món theo giá tăng dần; thử từng món $i$ làm món được tặng. Khi đó mọi món khác trong giỏ phải đứng sau $i$ trong thứ tự (giá $\ge c_i$; món cùng giá đứng sau cũng được), và phải chọn thêm ít nhất 2 món. Đây là bài cái túi trên các món sau $i$, với hai mảng: $H_1[b]$ = độ vui lớn nhất khi đã chọn thêm đúng 1 món, $H_2[b]$ = khi đã chọn thêm từ 2 món trở lên, tổng tiền $\le b$. Đáp án ứng với $i$ là $v_i + H_2[B]$.
Mỗi món $i$ chạy một bài cái túi $O(N \cdot B)$, tổng $O(N^2 \cdot B)$: với $N = 100$, $B = 10^4$ là $10^8$ phép tính đơn giản — chạy kịp. Với $N = 2000$ thì gấp 400 lần, quá chậm.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = -1e18;
int main() {
int n, B;
cin >> n >> B;
vector<pair<int, ll>> a(n); // (gia, do vui)
for (auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end()); // gia tang dan
ll ans = 0;
// mua 1 hoac 2 mon: tra du tien
for (int i = 0; i < n; i++) {
if (a[i].first <= B) ans = max(ans, a[i].second);
for (int j = i + 1; j < n; j++)
if (a[i].first + a[j].first <= B) ans = max(ans, a[i].second + a[j].second);
}
// mua >= 3 mon: thu tung mon i lam mon re nhat (duoc tang),
// cac mon con lai chon trong cac mon dung SAU i (gia >= gia mon i), it nhat 2 mon
vector<ll> H1(B + 1), H2(B + 1); // da chon them 1 mon / >= 2 mon
for (int i = 0; i < n; i++) {
fill(H1.begin(), H1.end(), NEG);
fill(H2.begin(), H2.end(), NEG);
for (int j = i + 1; j < n; j++) {
int c = a[j].first; ll v = a[j].second;
for (int b = B; b >= c; b--) {
H2[b] = max(H2[b], max(H2[b - c], H1[b - c]) + v);
H1[b] = max(H1[b], v);
}
}
ans = max(ans, a[i].second + H2[B]);
}
cout << ans << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); B = int(data[1])
a = sorted(zip(map(int, data[2:2 * n + 2:2]), map(int, data[3:2 * n + 3:2]))) # gia tang dan
NEG = -10 ** 18
ans = 0
# mua 1 hoac 2 mon: tra du tien
for i in range(n):
if a[i][0] <= B:
ans = max(ans, a[i][1])
for j in range(i + 1, n):
if a[i][0] + a[j][0] <= B:
ans = max(ans, a[i][1] + a[j][1])
# mua >= 3 mon: thu tung mon i lam mon re nhat (duoc tang),
# cac mon con lai chon trong cac mon dung SAU i, it nhat 2 mon
for i in range(n):
H1 = [NEG] * (B + 1) # da chon them 1 mon
H2 = [NEG] * (B + 1) # da chon them >= 2 mon
for j in range(i + 1, n):
c, v = a[j]
for b in range(B, c - 1, -1):
t = max(H2[b - c], H1[b - c]) + v
if t > H2[b]:
H2[b] = t
if v > H1[b]:
H1[b] = v
ans = max(ans, a[i][1] + H2[B])
print(ans)
main()Cách 3Một lượt cái túi với 5 trạng thái – O(N · B) · 100%
Ở Cách 2, ta chạy lại cái túi cho từng món được tặng. Nhưng nhìn Hình 1: khi xét các món theo giá tăng dần, "món được tặng" chỉ là món đầu tiên được chọn. Vậy gộp tất cả vào một lượt duy nhất, với trạng thái ghi nhớ giỏ đang ở "giai đoạn" nào. Với mọi $b$ từ $0$ tới $B$ (tổng tiền phải trả $\le b$):
| Mảng | Ý nghĩa | Khi gặp món (c, v) mới |
|---|---|---|
| P1[b] | giỏ có đúng 1 món, trả đủ tiền | chọn món này làm món duy nhất: $v$ (nếu $c \le b$) |
| P2[b] | giỏ có đúng 2 món, trả đủ tiền | từ P1[b − c] + v |
| F1[b] | giỏ khuyến mãi, mới có 1 món (món rẻ nhất, miễn phí) | chọn món này làm món đầu tiên: $v$, không tốn tiền |
| F2[b] | giỏ khuyến mãi, có 2 món | từ F1[b − c] + v |
| F3[b] | giỏ khuyến mãi, có từ 3 món | từ F2[b − c] + v hoặc F3[b − c] + v |
Trạng thái "không thể" gán $-10^{18}$. Như cái túi 0/1, vòng $b$ chạy giảm dần để mỗi món chỉ được dùng một lần (các ô $b - c$ vẫn còn giá trị "trước khi xét món này"); và trong cùng một $b$, ta cập nhật F3 trước F2, F2 trước F1, P2 trước P1 để mỗi phép gán chỉ dùng giá trị cũ. Đáp án là $$\max(0,\ P1[B],\ P2[B],\ F3[B]).$$
F1 và F2 không được tính vào đáp án: giỏ chưa đủ 3 món thì không có khuyến mãi. Không có trạng thái "P3" vì giỏ từ 3 món luôn được khuyến mãi (đã nằm trong F3).
Chạy tay ví dụ
Thứ tự xét: $(7, 6), (9, 5), (11, 19), (12, 19), (16, 19), (18, 9)$. Theo dõi giỏ tốt nhất $\{11, 12, 16\}$: khi gặp món $11$, giỏ vào trạng thái F1 với độ vui $19$, tiền $0$; gặp món $12$: F2, độ vui $38$, tiền $12$; gặp món $16$: F3, độ vui $57$, tiền $28 \le 29$. Vậy $F3[29] \ge 57$. Các giỏ khác: không món đơn lẻ hay cặp món nào (P1, P2) vượt $38$; và mọi giỏ từ 3 món có độ vui lớn hơn đều phải trả quá $29$ (ví dụ $\{11, 12, 16, 18\}$ phải trả $12 + 16 + 18 = 46$).
- Sắp xếp sai chiều: xét món đắt trước thì món đầu tiên được chọn là món đắt nhất — thành "tặng món đắt nhất", sai đề và luôn cho đáp án lớn hơn hoặc bằng đáp án đúng.
- Quên điều kiện 3 món: lấy cả F1, F2 vào đáp án là cho phép mua 1–2 món mà vẫn được tặng.
long long: tổng độ vui tới $2000 \cdot 10^9 = 2\cdot10^{12}$.
Mô phỏng dưới đây xét lần lượt từng món (đã sắp xếp) và cho xem cả năm mảng sau mỗi món.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = -1e18; // "khong the"
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, B;
cin >> n >> B;
vector<pair<int, ll>> a(n); // (gia, do vui)
for (auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end()); // xet mon RE truoc: mon dau tien duoc chon la mon re nhat
// P1, P2: da mua 1 / 2 mon, tra tien du (khong khuyen mai)
// F1, F2, F3: nhanh khuyen mai - mon dau tien (re nhat) duoc tang; da chon 1 / 2 / >= 3 mon
// X[b] = tong do vui lon nhat khi tong tien phai tra <= b
vector<ll> P1(B + 1, NEG), P2(B + 1, NEG), F1(B + 1, NEG), F2(B + 1, NEG), F3(B + 1, NEG);
for (auto [c, v] : a) {
for (int b = B; b >= 0; b--) { // b giam dan: moi mon chi mua 1 lan
if (b >= c) {
F3[b] = max(F3[b], max(F3[b - c], F2[b - c]) + v);
F2[b] = max(F2[b], F1[b - c] + v);
P2[b] = max(P2[b], P1[b - c] + v);
P1[b] = max(P1[b], v);
}
F1[b] = max(F1[b], v); // mon re nhat: mien phi
}
}
ll ans = max({0LL, P1[B], P2[B], F3[B]}); // F1, F2 chua du 3 mon -> khong hop le
cout << ans << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); B = int(data[1])
a = sorted(zip(map(int, data[2:2 * n + 2:2]), map(int, data[3:2 * n + 3:2])))
NEG = -10 ** 18 # "khong the"
# xet mon RE truoc: mon dau tien duoc chon la mon re nhat
# P1, P2: da mua 1 / 2 mon, tra tien du; F1, F2, F3: nhanh khuyen mai (mon re nhat duoc tang)
# X[b] = tong do vui lon nhat khi tong tien phai tra <= b
# F1[b] nhu nhau voi moi b (mon dau tien mien phi) -> chi can mot bien f1
P1 = [NEG] * (B + 1); P2 = [NEG] * (B + 1)
F2 = [NEG] * (B + 1); F3 = [NEG] * (B + 1)
f1 = NEG
for c, v in a:
for b in range(B, c - 1, -1): # b giam dan: moi mon chi mua 1 lan
t = F3[b - c]
u = F2[b - c]
if u > t:
t = u
t += v
if t > F3[b]:
F3[b] = t
t = f1 + v # F1[b - c] = f1 (gia tri CU, truoc mon nay)
if t > F2[b]:
F2[b] = t
t = P1[b - c] + v
if t > P2[b]:
P2[b] = t
if v > P1[b]:
P1[b] = v
if v > f1:
f1 = v # mon re nhat: mien phi
print(max(0, P1[B], P2[B], F3[B])) # F1, F2 chua du 3 mon -> khong hop le
main()b chạy giảm dần và cập nhật thẳng trên mảng (chỉ cần chạy từ $B$ xuống $c$, vì với $b < c$ chỉ có F1 thay đổi). Mảng F1 có mọi ô bằng nhau (độ vui lớn nhất trong các món đã xét) nên thay bằng một biến f1, cập nhật sau vòng b để trong vòng vẫn là giá trị cũ. Nộp bằng PyPy 3 thì vòng lặp đơn giản kiểu này chạy rất nhanh.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 32 test: Subtask 1 có 10 test ($N \le 15$; gồm ví dụ, $B = 0$, ba món chỉ mua đủ tiền nhờ được tặng, giỏ "chưa đủ 3 món"...), Subtask 2 có 10 test ($N \approx 100$, $B$ tới $10^4$, có test mọi món đắt hơn nửa số tiền), Subtask 3 có 12 test ($N \approx 2000$, $B \approx 10^4$). Các kiểu: ngẫu nhiên, độ vui tỉ lệ với giá (cái túi "khó"), nhiều món cùng giá, vài món cực đắt cực vui, nhiều món đắt hơn cả số tiền mang theo, độ vui gần $10^9$ (đáp án tới $4{,}6\cdot10^{11}$). Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (10 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Thử mọi tập con | Đúng 10/10 | 0/10 | 0/12 | 20 |
| Cách 2 – Thử từng món được tặng, $O(N^2 B)$ | Đúng 10/10 | Đúng 10/10 | TLE 0/12 | 50 |
| Cách 3 – QHĐ 5 trạng thái, $O(NB)$ (chuẩn) | Đúng 10/10 | Đúng 10/10 | Đúng 12/12 | 100 |
| Sai: sắp xếp giảm dần (tặng món đắt nhất) | WA 5/10 | WA 2/10 | WA 0/12 | 16 |
| Sai: quên điều kiện "từ 3 món" | WA 7/10 | WA 8/10 | WA 10/12 | 79,7 |
Sai: dùng int | WA 6/10 | WA 3/10 | WA 4/12 | 37,7 |
| Sai: vòng $b$ tăng dần (một món mua nhiều lần) | WA 2/10 | WA 2/10 | WA 0/12 | 10 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1, còn từ Subtask 2 thì $2^{100}$ tập con là không thể duyệt (code dùng 1 << n còn bị tràn, ra kết quả sai); Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3 (đo đủ thì mỗi test mất 18–40 giây); Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,1 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test (nên nộp bằng PyPy 3). Lỗi "quên điều kiện 3 món" là lỗi khó thấy nhất: vẫn được gần 80% số điểm, nhưng mất trọn những test mà giỏ tốt nhất chỉ có 1–2 món. Ví dụ của đề được chọn sao cho cả bốn lời giải sai trong bảng đều ra đúng $57$.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét