Dãy nhị phân 1
Đề bài
Hệ nhị phân (hay hệ đếm cơ số hai) là một hệ đếm dùng hai ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Hai ký tự đó thường là 0 và 1; chúng thường được dùng để biểu đạt hai giá trị hiệu điện thế tương ứng (có hiệu điện thế, hoặc hiệu điện thế cao là 1 và không có, hoặc thấp là 0). Do có ưu điểm tính toán đơn giản, dễ dàng thực hiện về mặt vật lý, chẳng hạn như trên các mạch điện tử, hệ nhị phân trở thành một phần kiến tạo căn bản trong các máy tính đương thời.
Trong bài tập này bạn được cho một số nguyên dương $n$, bạn cần tìm và in ra danh sách các dãy nhị phân có độ dài đúng $n$.
Dữ liệu vào:
- Gồm một dòng chứa số nguyên dương $n$.
Kết quả:
- Mỗi dòng in một dãy nhị phân độ dài $n$ tìm được. Các dãy nhị phân in tăng dần theo thứ tự từ điển.
Ràng buộc: $1 \le n \le 20$.
200
01
10
11Lời mở đầu
Đây là bài "Hello World" của chương Quay lui: điền lần lượt từng vị trí, ở mỗi vị trí thử hết các lựa chọn, điền xong thì in ra, rồi lùi lại để thử lựa chọn khác. Bài không có điều kiện gì nên cây quay lui đầy đủ, chưa phải cắt nhánh. Nhưng có một cái bẫy rất "đời": bộ test thật cho $n$ tới 24 (vượt ràng buộc đề), tức là phải in ra gần 17 triệu dòng – hơn 400 MB chỉ trong 1 giây. Bài này vì vậy cũng là bài học về cách in nhanh.
Trong contest có 3 bài "Dãy nhị phân" na ná nhau. Các bạn xem bảng dưới để thấy chúng khác nhau chỗ nào nhé:
| Bài | Điều kiện của dãy | In số lượng? | Giới hạn | Số dãy cần in | Điểm mấu chốt |
|---|---|---|---|---|---|
| Dãy nhị phân 1 (bài này) | Không có – in tất cả $2^n$ dãy | Không | $1 \le n \le 20$ (test thật tới 24) | $2^n$ | Thuần quay lui, không cắt nhánh; khó ở chỗ in nhanh hàng trăm MB |
| Dãy nhị phân 2 | Cụm 01 xuất hiện không quá 1 lần | Có (dòng đầu) | $1 \le n \le 100$ | $(n+1) + \binom{n+1}{3}$ | Bắt buộc cắt nhánh (không thể duyệt $2^{100}$); cần nhớ số cụm 01 đã có |
| Dãy nhị phân 3 | Không có hai số 1 đứng cạnh nhau | Có (dòng đầu) | $1 \le n \le 25$ | Fibonacci $F_{n+2}$ | Cắt nhánh chỉ cần nhìn ký tự ngay trước; sinh hết rồi lọc vẫn kịp trong C++ |
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 24 test, mỗi test chỉ một số $n$: test 1 là $n = 2$ (test đề), test 2 là $n = 1$, các test còn lại $n$ đúng bằng số thứ tự test (test 3 có $n = 3$, …, test 24 có $n = 24$). Output có $2^n$ dòng, mỗi dòng $n$ ký tự:
| Test | $n$ | Số dòng output lớn nhất | File output lớn nhất |
|---|---|---|---|
| 1 – 10 | 1 … 10 | 1.024 | 12,3 KB |
| 11 – 20 | 11 … 20 | 1.048.576 | 23,1 MB |
| 21 – 24 | 21 … 24 | 16.777.216 | 436,2 MB |
Đề không chia subtask, mình chia theo độ lớn của $n$ để so sánh các cách:
| Mức | Điều kiện | Các test | Cách 1endl | Cách 2'\n' | Cách 3 in cả dòng | Python |
|---|---|---|---|---|---|---|
| 1 | $n \le 10$ | 1 – 10 | 10/10 | 10/10 | 10/10 | 10/10 |
| 2 | $11 \le n \le 20$ | 11 – 20 | 9/10 | 10/10 | 10/10 | 10/10 |
| 3 | $21 \le n \le 24$ (vượt đề) | 21 – 24 | 0/4 | 0/4 | 4/4 | 0/4 |
Ý tưởngQuay lui: điền từng vị trí, thử 0 rồi thử 1
Ta xây dãy $s_1 s_2 \dots s_n$ từ trái sang phải bằng hàm đệ quy Try(i) = "điền vị trí thứ $i$":
Try(i): với mỗi giá trị $j$ trong $\{0, 1\}$ (thử 0 trước, 1 sau): gán $s_i = j$; nếu $i = n$ thì in dãy, ngược lại gọi Try(i + 1). Khi Try(i + 1) trả về, vòng lặp tự chuyển sang giá trị tiếp theo – đó chính là bước quay lui.Vì sao kết quả tự động tăng dần theo thứ tự từ điển? Hai dãy khác nhau lần đầu ở vị trí $i$ thì dãy có $s_i = 0$ nhỏ hơn – và ở vị trí $i$ ta luôn thử 0 trước, đi hết toàn bộ nhánh 0 rồi mới sang nhánh 1. Vậy chỉ cần thử các giá trị theo thứ tự tăng dần là xong, không phải sắp xếp gì cả.
Các lời gọi đệ quy tạo thành một cây quay lui: gốc là dãy rỗng, mỗi tầng điền thêm một vị trí, mỗi lá là một dãy hoàn chỉnh. Em nhập $n$ rồi bấm Tiếp để xem máy đi trên cây (đường màu cam là các lời gọi đang nằm trong ngăn xếp):
Cây có $2^n$ lá, mỗi lá in $n$ ký tự nên độ phức tạp là $O(n \cdot 2^n)$ – không thể nhỏ hơn được vì riêng lượng chữ cần in đã là $n \cdot 2^n$. Phần còn lại của bài là làm sao để in nhanh.
Cách 1Quay lui chuẩn sách giáo khoa, in bằng endl
Đây là cách viết mà hầu hết các bạn sẽ viết đầu tiên: mảng a[1..n] kiểu int, đủ $n$ vị trí thì dùng vòng lặp in từng số rồi endl.
for(int j = 0; j <= 1; j++): thử lần lượt 0 rồi 1 – thứ tự này đảm bảo thứ tự từ điển.if(i == n): vừa điền xong vị trí cuối thì in luôn; ngược lại gọiTry(i + 1). Không cần "xoá"a[i]khi quay lui vì lần sau sẽ ghi đè.endl= xuống dòng + xả bộ đệm (flush): mỗi dòng là một lần chương trình nhờ hệ điều hành ghi ra – với 16 triệu dòng thì rất chậm.
Kết quả chạy thật (cách 1, C++): đúng 19/24 test; quá thời gian ở các test 20–24 (test chậm nhất mất 4,7 giây, giới hạn chỉ 1 giây).
Bản Python (cùng ý tưởng, gom các dòng lại rồi in một lần ở cuối) đúng 20/24 test, quá thời gian ở test 21–24 – Python không thể in hàng trăm MB trong 1 giây.
Cách 2Bỏ endl, dùng '\n' và tắt đồng bộ
Mẹo quen thuộc: thêm ios::sync_with_stdio(0); cin.tie(0); và thay endl bằng '\n' để chữ được gom trong bộ đệm, đầy mới ghi một lần.
Kết quả chạy thật (cách 2, C++): đúng 20/24 test; quá thời gian ở các test 21–24 (test chậm nhất mất 5,0 giây, giới hạn chỉ 1 giây).
Nhanh hơn một chút nhưng vẫn chưa đủ: chương trình vẫn gọi cout << a[k] cho từng chữ số – tổng cộng $n \cdot 2^n \approx 400$ triệu lần gọi cout với $n = 24$, mà mỗi lần gọi là một lần đổi số int ra chữ.
Cách 3Giữ sẵn cả dòng trong mảng char, in một phát
Ý tưởng: lưu dãy dưới dạng mảng ký tự s[0..n-1], và đặt sẵn s[n] = '\n'. Khi đủ $n$ ký tự, cả dòng đã nằm liền nhau trong bộ nhớ, chỉ cần một lệnh fwrite(s, 1, n + 1, stdout) là in xong cả dòng (kể cả dấu xuống dòng). fwrite cũng có bộ đệm nên rất ít khi phải nhờ hệ điều hành.
- Lần này mình đặt điều kiện dừng ở đầu hàm:
if(i == n)nghĩa là đã điền xong $s_0 \dots s_{n-1}$ → in rồireturn. Đây là cách viết quay lui thứ hai rất hay gặp, tương đương cách 1. - Vòng
for(char c = '0'; c <= '1'; c++)thử thẳng ký tự'0','1'nên không phải đổi số ra chữ khi in. s[n] = '\n'chỉ gán một lần trongmain, quay lui không bao giờ đụng tới ô này.
Kết quả chạy thật (cách 3, C++): đúng 24/24 test, test chậm nhất (test 24, $n = 24$) chỉ mất 0,37 giây. Full điểm! 🎉
endl) đúng 19/24, cách 2 ('\n') đúng 20/24, cách 3 (mảng char + fwrite) đúng 24/24, test nặng nhất ($n = 24$, 436 MB) mất 0,37 giây. Bản Python đúng 20/24. Bài học: khi output khổng lồ, đừng dùng endl và hãy in cả dòng một lần.
Nhận xét
Đăng nhận xét