Nuôi bò 1

Nguồn: CLUE OJ – Chương 20: Quay lui (VinhDinhCoder – BTKCOW1) Độ khó: Dễ Quay lui Tập con

Đề bài

Đón đầu xu hướng kinh doanh nông trại sạch, Sắn về quê bắt tay làm kinh doanh với mảnh đất quê hương An Lưu. Sắn bắt đầu làm nông trại với $N$ chú bò sữa. Theo số lượng thống kê, chú bò thứ $i$ sản xuất $a[i]$ đơn vị sữa mỗi ngày.

Sắn muốn hợp lý hóa quá trình vắt sữa bò của mình mỗi ngày, vì vậy anh ấy đã cài đặt một máy vắt sữa hoàn toàn mới trong chuồng của mình. Thật không may, máy hóa ra quá nhạy cảm: nó chỉ hoạt động bình thường nếu lũ bò được đem vào vắt có tổng lượng sữa đúng $M$ đơn vị mỗi ngày. Tức là nó chỉ chọn đúng một tập bò nào đó có tổng lượng sữa sản xuất là $M$ để vắt. Sắn đang muốn lựa chọn một tập ít con bò nhất cho đúng $M$ đơn vị sữa để đưa vào cho máy này. Bạn hãy tính giúp cho Sắn điều này.

Dữ liệu nhập:

• Dòng thứ nhất là hai số nguyên dương $n$ và $M$ $(1 \le n \le 20,\ 1 \le M \le 2 \cdot 10^9)$.
• Dòng thứ hai là $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^8)$ là sản lượng sữa của $n$ chú bò.

Kết quả: in hai số nguyên cách nhau dấu cách. Số thứ nhất là số tập bò thoả mãn có tổng lượng sữa là $M$. Số thứ hai là số lượng bò ít nhất của tập bò cho đúng $M$ đơn vị sữa. Nếu không tìm được đáp án thì in ra 0 0.

Ví dụ – input

5 5
1 2 3 4 5

Ví dụ – output

3 1

Giải thích ví dụ: có 3 tập bò cho đúng 5 đơn vị sữa là $\{5\}$, $\{1, 4\}$, $\{2, 3\}$; tập ít bò nhất là $\{5\}$ với 1 con.

Lời mở đầu

Bài này là "liệt kê tập con" quen thuộc: mỗi con bò được chọn hoặc không được chọn, $n \le 20$ nên có tối đa $2^{20} \approx 10^6$ tập – thử hết là xong. Mình làm 2 cách: duyệt bitmask và quay lui (có cắt nhánh khi tổng sữa đã vượt $M$). Chú ý dòng chữ đỏ trong đề: không có tập nào thì in 0 0.

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ức nÝ tưởngChọn / bỏCách 1BitmaskCách 2Quay lui

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

Test	$n$	$M$ lớn nhất	$a_i$ lớn nhất	Số tập nhiều nhất	Số test in "0 0"
1–30	5–10	30	10	39	1
31–70	15–15	92.272.471	97.015.236	17	1
71–100	20–20	50	50	75	0

Đề không ghi subtask; bộ test chia theo $n$ thành 3 mức như bảng. Có 2 test không có tập bò nào thoả mãn – phải in 0 0. Số tập thoả mãn nhiều nhất cũng chỉ vài chục nghìn, dùng int để đếm là đủ; tổng sữa tối đa $20 \cdot 10^8 = 2 \cdot 10^9$ thì vượt int một chút nên mình dùng long long cho tổng.

Mức	Điều kiện	Test	Cách 1 bitmask	Cách 2 quay lui
1	$n \le 10$	1–30	C++ qua, Python qua	C++ qua, Python qua
2	$n = 15$	31–70	C++ qua, Python qua	C++ qua, Python qua
3	$n = 20$	71–100	C++ qua (0,09 s), Python quá thời gian	C++ 0,005 s, Python 0,03 s

Ý tưởngCây chọn / không chọn và cắt nhánh

Hàm quay lui Try(i, s, k): đang xét con bò thứ $i$, các con trước đã chọn được $k$ con với tổng sữa $s$.

Try(i, s, k)

• Nếu $s > M$: dừng luôn (cắt nhánh) – vì $a_i > 0$, chọn thêm bò chỉ làm tổng tăng, không bao giờ quay về đúng $M$.
• Nếu $i > n$: đã quyết định xong cho mọi con bò. Nếu $s = M$ (và có ít nhất 1 con) thì tăng cnt, cập nhật mn = min(mn, k).
• Ngược lại thử 2 nhánh: chọn bò $i$ → Try(i + 1, s + a[i], k + 1), rồi không chọn → Try(i + 1, s, k).

Em nhập $M$ và sản lượng sữa rồi bấm Tiếp. Mỗi nút ghi tổng sữa $s$ hiện tại; nhánh trên là "chọn", nhánh dưới là "bỏ":

nút đang xéttập có tổng đúng Ms > M → cắt nhánhviền cam: đang trên ngăn xếp

M Sữa của từng con

Ví dụ nhanh:

Cách 1Duyệt bitmask mọi tập con

Mỗi mask từ $1$ đến $2^n - 1$ là một tập bò khác rỗng (bit $i$ bằng 1 thì chọn bò $i$). Tính tổng sữa của tập; nếu bằng $M$ thì đếm, và số bò của tập chính là số bit 1 – hàm __builtin_popcount(mask) đếm giúp ta.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi mask từ 1 đến 2^n − 1, tính tổng sữa của tập.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Test đề có n = 5 (31 mask) hơi dài nên khung này giới hạn n ≤ 4. Các bước của vòng for i được gộp vào dòng if(mask >> i & 1).

Không gian$O(n)$

Thời gian$O(2^n \cdot n)$

Kết quả chạy thật: C++ đúng 100/100 test, chậm nhất 0,092 giây. Python cùng ý tưởng chỉ đúng 70/100: 30 test $n = 20$ phải làm $2^{20} \cdot 20 \approx 2 \cdot 10^7$ phép tính, Python mất hơn 3 giây → quá thời gian.

Cách 2Quay lui cộng dồn + cắt nhánh

C++▶ Chạy tay từng dòng codeCách 2: Try(i, s, k) chọn rồi bỏ từng con bò, cắt nhánh khi s > M.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung bên phải là ngăn xếp lời gọi: mỗi tầng ghi con bò đang xét và nhánh đang đi (chọn/bỏ).

1. Dòng if(s > M) return; đặt ngay đầu hàm là chỗ cắt nhánh: các test lớn có $M$ nhỏ hơn nhiều so với tổng sữa, nên phần lớn cây bị cắt từ rất sớm.
2. Điều kiện k > 0 để không đếm tập rỗng (thật ra $M \ge 1$ nên tập rỗng không bao giờ có tổng $M$, viết thêm cho chắc).
3. Không tìm thấy tập nào thì cnt = 0 → in 0 0 đúng yêu cầu đề.

Không gian$O(n)$ (độ sâu đệ quy)

Thời gian$O(2^n)$, thực tế ít hơn nhiều nhờ cắt nhánh

Kết quả chạy thật: C++ đúng 100/100 test, chậm nhất 0,005 giây (nhanh hơn cách 1 gần 20 lần nhờ cộng dồn và cắt nhánh). Python cũng 100/100, chậm nhất 0,03 giây.

Ghi chú của mình: cách 1 (bitmask) C++ 100/100, Python 70/100 (quá thời gian ở 30 test $n = 20$); cách 2 (quay lui cắt nhánh) cả C++ và Python đều 100/100.

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 😇