Dãy nhị phân 3
Đề 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$ thoả mãn điều kiện không có hai số 1 đứng cạnh nhau.
Dữ liệu vào:
- Gồm một dòng chứa số nguyên dương $n$.
Kết quả:
- Dòng đầu tiên ghi một số nguyên dương $m$ là số lượng dãy nhị phân tìm được.
- Mỗi dòng tiếp theo 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 25$.
35
000
001
010
100
101Lời mở đầu
Bài này là bước tiếp theo sau Dãy nhị phân 1: vẫn là cây quay lui điền từng vị trí bằng 0 hoặc 1, nhưng giờ có điều kiện "không có 11". Đây là dịp tốt để làm quen với kỹ thuật quan trọng nhất của quay lui: cắt nhánh – phát hiện sai càng sớm càng tốt, không đi tiếp vào những nhánh chắc chắn hỏng. Bảng dưới so sánh 3 bài dãy nhị phân trong contest:
| 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 | 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 (bài này) | 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ó 25 test, mỗi test một số $n$: test 1 là $n = 3$ (test đề), test 2 là $n = 2$, test 3 là $n = 1$, các test 4 – 25 có $n$ đúng bằng số thứ tự test. Đúng ràng buộc đề, không có gì bất thường. Số dãy cần in tăng theo dãy Fibonacci (5, 8, 13, 21, …):
| Test | $n$ | Số dãy lớn nhất | File output lớn nhất |
|---|---|---|---|
| 1 – 20 | 1 … 20 | 17.711 | 0,4 MB |
| 21 – 25 | 21 … 25 | 196.418 | 5,3 MB |
Đề không chia subtask; mình chia 2 mức theo $n$ để thấy khác biệt giữa các cách:
| Mức | Điều kiện | Các test | Cách 1 C++ sinh hết rồi lọc | Cách 1 Python | Cách 2 C++ cắt nhánh | Cách 2 Python |
|---|---|---|---|---|---|---|
| 1 | $n \le 20$ | 1 – 20 | 20/20 | 20/20 | 20/20 | 20/20 |
| 2 | $21 \le n \le 25$ | 21 – 25 | 5/5 | 1/5 | 5/5 | 5/5 |
Ý tưởngĐặt số 1 chỉ khi ngay trước nó là số 0
Cách "ngây thơ": sinh cả $2^n$ dãy như bài Dãy nhị phân 1, đủ $n$ ký tự rồi mới kiểm tra có 11 không. Nhưng nghĩ một chút: nếu đã đặt 1 ở vị trí $i-1$ mà lại đặt tiếp 1 ở vị trí $i$ thì dãy chắc chắn hỏng, dù các vị trí sau có điền gì đi nữa. Vậy cắt luôn nhánh đó:
0; chỉ được đặt 1 khi $i = 0$ (vị trí đầu) hoặc $s_{i-1} = $ 0. Nhờ vậy mọi lá của cây đều là dãy hợp lệ, không phải kiểm tra gì ở cuối nữa.Thứ tự từ điển vẫn được đảm bảo vì ở mỗi vị trí ta thử 0 trước rồi mới tới 1. Còn số lượng thì sao? Gọi $f(n)$ là số dãy hợp lệ độ dài $n$: dãy bắt đầu bằng 0 thì phần sau là dãy hợp lệ độ dài $n-1$; dãy bắt đầu bằng 1 thì bắt buộc tiếp theo là 0, phần sau là dãy hợp lệ độ dài $n-2$. Vậy $f(n) = f(n-1) + f(n-2)$ với $f(1) = 2$, $f(2) = 3$ – chính là dãy Fibonacci. Với $n = 25$ có $196\,418$ dãy.
Em nhập $n$, chọn có cắt nhánh (1) hoặc sinh hết rồi lọc (0), rồi bấm Tiếp để so sánh hai cây (nút đỏ có dấu ✗ là nhánh bị cắt, lá đỏ là dãy bị loại):
Cách 1Sinh hết $2^n$ dãy rồi lọc
Đi hết cây đầy đủ, đủ $n$ ký tự thì gọi ok() kiểm tra. Vì đề bắt in số lượng trước rồi mới in các dãy, mình gom các dãy hợp lệ vào xâu res và đếm bằng cnt, cuối cùng in cnt rồi in res.
Kết quả chạy thật: bản C++ đúng 25/25 test, chậm nhất 0,25 giây ($n = 25$: $2^{25} \approx 33{,}5$ triệu lá) – vẫn kịp vì ok() dừng ngay khi gặp 11 đầu tiên. Bản Python đúng 21/25 test, quá thời gian ở test 22–25.
Cách 2Quay lui có cắt nhánh
- Dòng
if(c == '1' && i > 0 && s[i - 1] == '1') continue;là toàn bộ "phép màu": không đặt1ngay sau1. Điều kiệni > 0đặt trước để không đọcs[-1]. - Khi
i == nthì dãy chắc chắn hợp lệ, chỉ việc đếm và lưu. - Mỗi nút trong cây đều dẫn tới ít nhất một lá (luôn có thể đặt
0), nên số lời gọi chỉ cỡ $n \cdot f(n)$ – không lãng phí.
Kết quả chạy thật: bản C++ đúng 25/25 test, chậm nhất chỉ 0,018 giây (nhanh hơn cách 1 khoảng 14 lần); bản Python cũng đúng 25/25, chậm nhất 0,20 giây. Full điểm! 🎉
Nhận xét
Đăng nhận xét