Phân tích thành tổng

Nguồn: CLUE OJ – Chương 20: Quay lui (VinhDinhCoder) Độ khó: Trung bình Quay lui Xuất dữ liệu lớn

Đề bài

Với một số nguyên dương $N$ ta có thể phân tích $N$ thành tổng của các số nguyên dương khác. Ví dụ với $N = 5$ ta có thể phân tích thành:

• 5 = 1+1+1+1+1
• 5 = 1+1+1+2
• 5 = 1+1+3
• 5 = 1+2+2
• 5 = 1+4
• 5 = 2+3

Hãy tìm tất cả các cách phân tích số $N$ thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là 1 cách.

Dữ liệu vào: gồm một số nguyên dương duy nhất là $N$ $(1 \le N \le 57)$.

Kết quả: in ra mỗi dòng là một cách phân tích. Thứ tự in ra theo output mẫu.

Ví dụ 1 – input

1

Ví dụ 1 – output

1 = 1

Ví dụ 2 – input

5

Ví dụ 2 – output

5 = 1+1+1+1+1
5 = 1+1+1+2
5 = 1+1+3
5 = 1+2+2
5 = 1+4
5 = 2+3
5 = 5

Lưu ý về đề và bộ test

• Danh sách ví dụ trong đề thiếu dòng 5 = 5, nhưng test mẫu (và bộ test) có in cách "chính nó": N = N. Với $N = 1$ đáp án là 1 = 1.
• Định dạng mỗi dòng: N = (có dấu cách hai bên dấu bằng), các số hạng nối bằng dấu + không có dấu cách.
• Đề ghi $N \le 57$ nhưng bộ test thật có $N$ tới 69 – output lên tới khoảng 148 MB. Vì vậy cách in ra quyết định tất cả!

Lời mở đầu

Thuật toán quay lui của bài này rất ngắn. Cái khó nằm ở chỗ khác: số cách phân tích tăng cực nhanh ($N = 69$ có hơn 3,5 triệu cách) nên chương trình phải in ra hàng trăm MB trong 1 giây. Mình sẽ đi từ code quay lui "chuẩn sách giáo khoa" tới bản tự quản lý bộ đệm xuất, chạy thật trên bộ test để các bạn thấy rõ mỗi bước tối ưu ăn thêm bao nhiêu test.

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ộ test69 testÝ tưởngkhông giảmCách 1cout + endlCách 2\n + syncCách 3bộ đệm

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

Mức (tự chia)	Test	Giá trị N	Số dòng output lớn nhất	Kích thước output lớn nhất
1	1–20	$N \le 20$	627	0.0 MB
2	21–57	$21 \le N \le 57$	614.154	22.9 MB
3	58–69	$58 \le N \le 69$	3.554.345	148.7 MB

Bộ test có 69 test, mỗi giá trị $N$ từ 1 đến 69 đúng một test (test 1–5 là $N$ = 1, 5, 3, 4, 2; từ test 6 trở đi test $t$ có $N = t$). Đề không chia subtask, mình chia 3 mức theo độ lớn của $N$. Mức 3 vượt giới hạn $N \le 57$ của đề. Kết quả chạy thật (giới hạn 1 giây):

Mức	Điều kiện	Test	Cách 1 (endl)	Cách 2 ("\n" + sync)	Cách 3 (bộ đệm)
1	$N \le 20$	1–20	20/20	20/20	20/20
2	$21 \le N \le 57$	21–57	37/37	37/37	37/37
3	$58 \le N \le 69$	58–69	0/12	3/12	12/12

Ý tưởngSố hạng không giảm

"Hoán vị của nhau chỉ tính 1 cách" – ta chọn một đại diện duy nhất cho mỗi cách: viết các số hạng theo thứ tự không giảm $a_1 \le a_2 \le \dots \le a_k$. Nhìn test mẫu thấy đúng như vậy, và các dòng được in theo thứ tự từ điển của dãy số hạng.

Quay lui

Try(con): còn thiếu tổng con. Nếu con = 0 thì in dãy hiện tại. Ngược lại thử số hạng tiếp theo $x$ từ $a_k$ (số hạng trước, để dãy không giảm) đến con, tăng dần; chọn $x$ rồi gọi Try(con − x), gọi xong thì bỏ $x$ ra.

Vì $x \le$ con nên mọi nhánh đều đi được tới con = 0 – không có ngõ cụt: số lá của cây quay lui đúng bằng số cách. Thử $x$ tăng dần nên các cách được in đúng thứ tự từ điển như output mẫu. Em chọn $N$ rồi bấm Tiếp để xem cây quay lui:

N =

Ví dụ nhanh:

Cách 1Quay lui + cout, endl

Cài đặt thẳng ý tưởng. Mảng a[1..k] lưu các số hạng; đặt a[0] = 1 để số hạng đầu tiên được thử từ 1.

C++▶ Chạy tay từng dòng codeCách 1: quay lui số hạng không giảm, in mỗi dòng bằng cout và endl.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. for(int x = a[k]; x <= con; x++): số hạng mới không nhỏ hơn số hạng trước – đây là điều kiện chống đếm trùng hoán vị.
2. a[++k] = x; … k--;: thêm rồi bỏ số hạng – bước quay lui.
3. Mỗi lần in một dòng ta in lại từ đầu cả dãy, và endl ép đẩy bộ đệm ra ngoài sau mỗi dòng.

Không gian$O(N)$

Thời gian$O(\text{tổng độ dài output})$ nhưng hằng số lớn

Kết quả chạy thật: Bản C++ đúng 57/69 test, quá thời gian ở test 58–69; test đúng chạy lâu nhất 0.95s.

Cách 2Bỏ endl, tắt đồng bộ nhập xuất

Thay endl bằng "\n" và thêm ios::sync_with_stdio(0); cin.tie(0); – hai thói quen cơ bản khi in nhiều.

C++▶ Chạy tay từng dòng codeCách 2: như cách 1 nhưng dùng "\n" và tắt đồng bộ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời giannhư cách 1, hằng số nhỏ hơn

Kết quả chạy thật: Bản C++ đúng 60/69 test, quá thời gian ở test 61–69; test đúng chạy lâu nhất 0.99s. Nhanh hơn một chút nhưng vẫn chưa đủ: với $N = 69$ phải in 148 MB, chuyển từng số nguyên thành chữ qua cout vẫn quá chậm.

Cách 3Giữ sẵn dòng đang xây + tự làm bộ đệm xuất

Hai nhận xét:

• Các dòng liên tiếp có tiền tố chung rất dài (vd 5 = 1+1+1+). Thay vì in lại cả dãy, ta giữ sẵn dòng đang xây trong mảng ký tự cur: chọn $x$ thì nối "+x" vào cuối, quay lui thì chỉ cần cắt độ dài về như cũ (cl = old). Khi con = 0 thì cả dòng đã sẵn, chép một lần là xong.
• Gom output vào mảng buf 64 KB, đầy mới gọi fwrite một lần – nhanh hơn nhiều so với in từng mẩu nhỏ.

C++▶ Chạy tay từng dòng codeCách 3: giữ sẵn dòng đang xây trong cur, gom output vào buf rồi fwrite một lần.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bộ đệm 64 KB không bao giờ đầy với N nhỏ, nên chỉ xả 1 lần ở cuối hàm main.

1. cl = sprintf(cur, "%d = ", n): dòng nào cũng bắt đầu bằng "N = ", sprintf trả về số ký tự đã ghi.
2. if(cur[cl - 1] != ' '): ký tự cuối là dấu cách nghĩa là chưa có số hạng nào → không thêm dấu +.
3. $N \le 69$ nên số hạng có tối đa 2 chữ số, ghi tay từng chữ số thay vì gọi hàm đổi số thành xâu.
4. int old = cl; … cl = old;: quay lui bằng cách "quên" phần đuôi, không phải xoá gì cả.

Không gian$O(N)$ + 64 KB bộ đệm

Thời gian$O(\text{tổng độ dài output})$, hằng số rất nhỏ

Kết quả chạy thật: Bản C++ đúng 69/69 test; test đúng chạy lâu nhất 0.18s. Còn bản Python đúng 53/69 test, quá thời gian ở test 54–69; test đúng chạy lâu nhất 0.78s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. cout + endl	C++	57/69	> 1s	Quá thời gian test 58–69 (N ≥ 58)
2. "\n" + sync	C++	60/69	> 1s	Quá thời gian test 61–69 (N ≥ 61)
3. Dòng đang xây + bộ đệm	C++	69/69	0.18s	Full
	Python	53/69	> 1s	Quá thời gian test 54–69 (N ≥ 54)

Ghi chú của mình: cả 3 cách có cùng một thuật toán quay lui, chỉ khác cách in. Nếu bộ test đúng như đề ($N \le 57$) thì cả cách 1 cũng qua; nhưng test thật lên tới $N = 69$ nên cách 1 và 2 trượt các test cuối vì output quá to; cách 3 giữ sẵn dòng đang xây và tự làm bộ đệm nên in 148 MB chỉ mất 0,18 giây. Python thì dù có tối ưu vẫn không thể in kịp hàng trăm MB trong 1 giây – bài này chỉ nên nộp C++.

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 😇