Dán tem

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (Phan Văn Việt) Độ khó: Trung bình Quy hoạch động Đổi tiền

Đề bài

Cho một tập hợp gồm $n$ loại tem, mỗi loại có một mệnh giá khác nhau. Một phong bì có thể dán tối đa $k$ con tem. Nhiệm vụ là tìm số nguyên dương lớn nhất $m$ sao cho mọi giá trị từ $1$ đến $m$ đều có thể tạo thành bằng cách dán không quá $k$ con tem từ tập mệnh giá đã cho.

Dữ liệu

• Dòng đầu gồm hai số nguyên $k$ và $n$ $(1 \le k \le 200;\ 1 \le n \le 50)$: số tem tối đa được dán trên mỗi phong bì và số loại tem.
• Dòng tiếp theo chứa $n$ số nguyên $a_i$ $(1 \le a_i \le 10^4)$, mỗi số là mệnh giá của một loại tem.

Kết quả

• Một dòng duy nhất là số nguyên $m$ lớn nhất sao cho từ $1$ đến $m$ đều có thể biểu diễn bằng không quá $k$ con tem. Nếu không có giá trị nào thỏa mãn thì in 0.

Ví dụ – input

5 2
1 3

Ví dụ – output

13

Giải thích ví dụ: có 2 loại tem mệnh giá $1$ và $3$, dán tối đa $k = 5$ con. Các giá trị $1, 2, \ldots, 13$ đều dán được, ví dụ $13 = 3 + 3 + 3 + 3 + 1$ (5 con). Nhưng $14$ cần ít nhất $3 + 3 + 3 + 3 + 1 + 1$ = 6 con tem > 5 → không dán được, nên $m = 13$. Mỗi loại tem được dùng bao nhiêu con cũng được.

Lưu ý: dòng đầu là $k$ trước, $n$ sau – rất dễ đọc nhầm thứ tự.

Lời mở đầu

Đây là một biến thể của bài đổi tiền (coin change) kinh điển: thay vì hỏi "đổi số tiền $s$ cần ít nhất mấy đồng xu", ta hỏi lần lượt cho $s = 1, 2, 3, \ldots$ và dừng ở tổng đầu tiên cần nhiều hơn $k$ con tem. Mình sẽ bắt đầu bằng cách quay lui liệt kê mọi cách dán (đủ cho các test nhỏ), rồi chuyển sang quy hoạch động $f[s]$ = số tem ít nhất để dán đúng tổng $s$.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test3 mứcCách 1Quay lui 30%Ý tưởngf[s]Cách 2QHĐ 100%

Bộ testBộ test chính thức có gì?

Test	$k$	$n$	$a_i$ lớn nhất	Đáp án
1–30	1–10	1–5	10	0 … 88
31–80	100–196	20–50	9.988	702.823 … 1.884.898
81–100	200–200	50–50	10.000	1.977.136 … 1.992.319

Đề không ghi subtask nhưng bộ test chia rõ 3 mức, mình tự đặt tên như bảng dưới. Mọi test đều có các mệnh giá khác nhau đôi một. Có 1 test (test 6) không có tem mệnh giá 1 → không dán được giá trị 1, đáp án là $0$. Đáp án lớn nhất gần $2 \cdot 10^6$ – đúng cỡ $k \cdot \max a_i = 200 \cdot 10^4$.

Mức	Điều kiện	Test	Cách 1 (quay lui)	Cách 2 (QHĐ)
1	$k \le 10,\ n \le 5,\ a_i \le 10$	1–30	qua	qua
2	$k \le 200,\ n \le 50$	31–80	quá thời gian	qua
3	$k = 200,\ n = 50,\ \max a_i = 10^4$	81–100	quá thời gian	qua

Cách 1Quay lui liệt kê mọi cách dán (mức 1)

Một cách dán là một tổ hợp lặp các loại tem: thứ tự dán không quan trọng, $1 + 3$ cũng như $3 + 1$. Để không đếm trùng, mình bắt các con tem được chọn theo thứ tự loại không giảm: hàm Try(i, cnt, sum) chỉ được chọn con tem tiếp theo có loại $j \ge i$. Mỗi trạng thái đi qua (kể cả khi đang dán dở) là một tổng dán được, đánh dấu ok[sum] = true. Cuối cùng đếm từ $1$ lên cho tới tổng đầu tiên chưa được đánh dấu.

C++▶ Chạy tay từng dòng codeCách 1: quay lui liệt kê tổ hợp lặp các con tem, đánh dấu mọi tổng dán được.

Dữ liệu vào (stdin) – sửa thoải mái3 2 1 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Test đề có 21 lời gọi nên khá dài; dữ liệu mặc định nhỏ hơn để dễ theo dõi (khung nhận k ≤ 4, n ≤ 3).

1. ok[0] cũng được đánh dấu (không dán con nào) nhưng vòng while bắt đầu kiểm tra từ $1$ nên không ảnh hưởng.
2. Số lời gọi bằng số tổ hợp lặp chọn $\le k$ con từ $n$ loại, tức $\binom{n + k}{k}$. Với $k = 10,\ n = 5$ chỉ khoảng $3\,000$; nhưng với $k = 200,\ n = 50$ thì là một số khổng lồ cỡ $10^{55}$.

Không gian$O(k \cdot \max a_i)$ (mảng đánh dấu)

Thời gian$O\left(\binom{n+k}{k}\right)$

Kết quả chạy thật: đúng 30/100 test – trọn mức 1, mỗi test chạy tức thì. Toàn bộ 70 test từ test 31 trở đi đều quá thời gian: với $k \ge 100$ và $n \ge 20$ số tổ hợp lặp là con số thiên văn. Bản Python cũng qua 30 test đầu (chậm nhất 0,02 giây).

Ý tưởng QHĐCon tem cuối cùng là con nào?

Gọi $f[s]$ là số con tem ít nhất để dán được đúng tổng $s$. Một cách dán tổng $s$ (với $s > 0$) chắc chắn có một con tem "cuối cùng" mệnh giá $a_i \le s$; bỏ con tem đó ra thì phần còn lại là một cách dán tổng $s - a_i$. Vậy:

Công thức truy hồi

$$f[0] = 0, \qquad f[s] = \min_{a_i \le s} \big(f[s - a_i] + 1\big)$$ Tổng $s$ dán được bằng không quá $k$ con tem $\iff f[s] \le k$. Đáp án là $m$ lớn nhất mà $f[1], f[2], \ldots, f[m]$ đều $\le k$.

Ta tính $f[1], f[2], \ldots$ theo thứ tự tăng dần và dừng ngay ở $s$ đầu tiên có $f[s] > k$; đáp án là $s - 1$. Vòng lặp chắc chắn dừng vì $k$ con tem chỉ dán được tổng tối đa $k \cdot \max a_i \le 2 \cdot 10^6$ – đó cũng là kích thước mảng cần dùng. Nếu không có tem mệnh giá 1 thì $f[1] = \infty > k$ và dừng ngay ở $s = 1$, in ra $0$ đúng như đề yêu cầu.

Em nhập $k$ và các mệnh giá rồi bấm Tiếp để xem mảng $f$ được điền dần. Ô vàng là ô đang tính, các ô xanh tím là $f[s - a_i]$ ứng với từng con tem cuối:

ô đang tínhf[s − a_i] được dùnglựa chọn tốt nhấtcần quá k tem → dừng

k Mệnh giá

Ví dụ nhanh:

Cách 2Quy hoạch động $f[s]$ (full điểm)

C++▶ Chạy tay từng dòng codeCách 2: tính f[1], f[2], ... cho tới tổng đầu tiên cần quá k con tem.

Dữ liệu vào (stdin) – sửa thoải mái5 2 1 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. f[s] = INT_MAX nghĩa là "chưa dán được". Phép f[s - a[i]] + 1 không bao giờ tràn số: mọi ô trước $s$ đều đã $\le k$ (nếu không thì vòng lặp đã dừng từ trước).
2. Mảng f khai báo toàn cục cỡ $2 \cdot 10^6 + 5$ (8 MB) – đủ cho tổng lớn nhất $k \cdot \max a_i + 1$.
3. Khi thoát vòng lặp, $s$ là tổng đầu tiên không dán được, nên in $s - 1$.

Không gian$O(k \cdot \max a_i)$

Thời gian$O(k \cdot \max a_i \cdot n) \approx 10^8$ phép tính đơn giản

Kết quả chạy thật: đúng 100/100 test, test chậm nhất ($k = 200$, $n = 50$, đáp án gần $2 \cdot 10^6$) mất 0,13 giây. Bản Python cùng ý tưởng đúng 30 test đầu nhưng với test lớn phải chạy khoảng $10^8$ bước, mất khoảng 2,4–2,7 giây (mình thử test 31–33 và 81–83) → quá thời gian 1 giây; các bạn dùng Python thì chỉ ăn được mức 1 ở bài này.

Ghi chú của mình: C++ – cách 1 (quay lui) 30/100, cách 2 (QHĐ) 100/100, chậm nhất 0,13 giây. Hai chỗ dễ sai: đọc nhầm thứ tự $k$ trước $n$ sau, và quên trường hợp không có tem mệnh giá 1 (test 6, đáp án 0) – cả hai code trên đều xử lý tự nhiên trường hợp này.

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 😇