Dãy ngoặc đúng 2
Đề bài
Người ta định nghĩa một dãy ngoặc đúng như sau:
- Xâu rỗng là một dãy ngoặc đúng.
- Nếu $A$ là dãy ngoặc đúng thì $(A)$ cũng là một dãy ngoặc đúng.
- Nếu $A$, $B$ là những dãy ngoặc đúng thì $AB$ cũng là dãy ngoặc đúng.
Những dãy ngoặc sau được xem là đúng: ()(()), ((())).
Những dãy ngoặc sau thì không: )(, ((()), )()(.
Nhiệm vụ của bạn trong bài tập này là liệt kê tất cả các dãy ngoặc đúng độ dài $n$.
Dữ liệu vào:
- Dòng thứ nhất là số nguyên dương $n$.
Kết quả:
- Dòng đầu tiên ghi số lượng dãy ngoặc đúng độ dài $n$.
- Các dòng tiếp theo mỗi dòng ghi một dãy ngoặc đúng độ dài $n$ theo thứ tự từ điển.
Ràng buộc: $1 \le n \le 27$.
42
(())
()()Lời mở đầu
Bài này "họ hàng" rất gần với các bài Dãy nhị phân trong cùng contest: thay 0/1 bằng (/), và điều kiện bây giờ là "ngoặc đúng". Nếu sinh hết $2^n$ dãy rồi kiểm tra thì $n = 30$ sẽ có hơn 1 tỉ dãy – không kịp. Mình sẽ dùng hai bộ đếm (số ngoặc mở, số ngoặc đóng đã đặt) để cắt nhánh ngay từ đầu, sao cho mọi lá của cây quay lui đều là dãy đúng.
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ó 30 test, mỗi test một số $n$: test 1 là $n = 4$ (test đề), test 2 là $n = 2$, test 3 là $n = 3$, test 4 là $n = 1$, các test 5 – 30 có $n$ bằng số thứ tự test. Một nửa số test có $n$ lẻ – khi đó đáp án chỉ là một dòng 0.
| Test | $n$ | Số test $n$ lẻ (đáp án 0) | Số dãy lớn nhất | File output lớn nhất |
|---|---|---|---|---|
| 1 – 20 | 1 … 20 | 10 | 16.796 | 0,4 MB |
| 21 – 27 | 21 … 27 | 4 | 742.900 | 20,8 MB |
| 28 – 30 | 28 … 30 | 1 | 9.694.845 | 310,2 MB |
Đề không chia subtask; mình chia 3 mức theo $n$:
| 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 27$ | 21 – 27 | 5/7 | 0/7 | 7/7 | 7/7 |
| 3 | $28 \le n \le 30$ (vượt đề) | 28 – 30 | 0/3 | 0/3 | 3/3 | 1/3 |
Ý tưởngHai bộ đếm: còn được mở không, có gì để đóng không
Một dãy ngoặc độ dài $n$ là đúng khi và chỉ khi: đọc từ trái sang phải, số ngoặc đóng không bao giờ vượt số ngoặc mở, và cuối cùng hai số bằng nhau (mỗi loại đúng $n/2$ cái). Từ đó, khi điền vị trí $i$ với mo ngoặc mở và dong ngoặc đóng đã đặt:
( khi mo < n/2 (chưa dùng hết ngoặc mở).Được đặt
) khi dong < mo (còn ngoặc mở đang chờ được đóng).Theo hai quy tắc này, đi tới vị trí cuối cùng thì luôn có
mo = dong = n/2 → mọi lá đều là dãy ngoặc đúng.Thứ tự từ điển: trong bảng mã ASCII, ( có mã 40, ) có mã 41, nên ( < ). Ở mỗi vị trí ta thử ( trước rồi mới ) là kết quả tự tăng dần – đúng như ví dụ: (()) đứng trước ()().
Số lượng: số dãy ngoặc đúng có $h = n/2$ cặp là số Catalan $C_h = \dfrac{1}{h+1}\binom{2h}{h}$: $C_1 = 1,$ $C_2$ $= 2,$ $C_3$ $= 5,$ $C_4$ $= 14,$ $\dots,$ $C_{15}$ $= 9\,694\,845$. Nếu $n$ lẻ thì không có dãy nào, in 0. Tính được số lượng trước nên ta in ngay dòng đầu, rồi vừa quay lui vừa in, không phải lưu gì.
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 để xem cây quay lui (nút đỏ ✗ là nhánh bị cắt, lá đỏ là dãy bị loại):
Cách 1Sinh hết $2^n$ dãy rồi kiểm tra
Đi hết cây đầy đủ, mỗi lá kiểm tra bằng biến bal (số ngoặc mở đang chờ đóng): gặp ( tăng 1, gặp ) giảm 1, nếu có lúc âm hoặc cuối cùng khác 0 thì sai. Dãy đúng thì đếm và gom vào xâu res để in sau dòng số lượng.
Kết quả chạy thật: bản C++ đúng 25/30 test, quá thời gian ở test 26–30 – để ý cả test $n$ lẻ (27, 29) cũng TLE dù đáp án chỉ là 0, vì cách này vẫn cặm cụi sinh đủ $2^n$ dãy. Bản Python đúng 20/30 test, TLE từ test 21 trở đi.
Cách 2Quay lui cắt nhánh + đếm trước bằng số Catalan
if(n % 2 == 1): $n$ lẻ thì in0và dừng luôn.- Vòng
fortính $\binom{2h}{h}$ theo kiểucat = cat * (h + k) / k: sau bước $k$,cat$= \binom{h+k}{k}$ nên phép chia luôn chia hết; cuối cùng chia cho $h + 1$ được số Catalan. Với $h = 15$ giá trị lớn nhất cỡ $1{,}5 \cdot 10^8$,long longthoải mái. - Trong
Try: haiifđộc lập (không phảielse) vì có những vị trí đặt được cả hai loại ngoặc. Thứ tự(trước,)sau đảm bảo thứ tự từ điển. - Như bài Dãy nhị phân 1, dãy đang xây là mảng
charcó sẵn'\n'ở cuối, đủ $n$ ký tự thìfwritecả dòng – in 310 MB vẫn nhanh.
Kết quả chạy thật: bản C++ đúng 30/30 test, test nặng nhất ($n = 30$) chỉ mất 0,28 giây. Full điểm! 🎉 Bản Python (in theo từng khối 65 536 dòng) đúng 28/30 test, chỉ TLE ở test 28 và 30 – hai test vượt ràng buộc đề với 2,7 triệu và 9,7 triệu dòng.
mo < n/2, dong < mo) và khi đề bắt in số lượng trước mà output quá lớn thì tính số lượng bằng công thức (số Catalan) thay vì lưu hết kết quả.
Nhận xét
Đăng nhận xét