Editorial for Bà Nội Đan Len
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Nghaiz
Lời giải: Bà Nội Đan Len
Chủ đề: xử lý chuỗi (string), ngăn xếp bằng list chứa tuple
Tóm tắt đề
Khai triển một công thức dạng 2[x3[yz]]w, trong đó n[S] nghĩa là lặp \(S\) đúng \(n\) lần, các cặp ngoặc có thể lồng nhau.
Ý tưởng 1: đệ quy (đúng nhưng nguy hiểm)
Cấu trúc lồng nhau gợi ý ngay tới đệ quy: hàm doc() đọc một công thức cho tới khi gặp ]. Mỗi khi gặp n[ thì gọi đệ quy doc() để đọc phần bên trong, rồi nhân lên \(n\) lần.
Cách này đúng, nhưng công thức dài \(10^4\) ký tự có thể lồng sâu tới hơn \(3000\) tầng (ví dụ 1[1[1[...1[a]...]]]). Giới hạn đệ quy mặc định của Python là \(1000\) tầng nên chương trình bị RecursionError → IR. Muốn dùng đệ quy thì phải thêm sys.setrecursionlimit(...).
Ý tưởng 2: tự quản lý ngăn xếp (an toàn)
Thay vì để Python tự nhớ "đang ở tầng nào" qua các lời gọi hàm, ta tự nhớ bằng một list dùng làm ngăn xếp. Duyệt từng ký tự:
- Chữ số: ghép vào số đang đọc,
so = so * 10 + int(ch). Số có thể có nhiều chữ số như10hay1000000000. - Dấu
[: sắp vào một tầng mới. Cất tầng hiện tại cùng số lần lặp vào ngăn xếp dưới dạng mộttuple(hien_tai, so), rồi bắt đầu tầng mới rỗng. - Dấu
]: kết thúc tầng hiện tại. Lấy tầng ngoài ra khỏi ngăn xếp, rồi nối thêm vào nó chuỗi của tầng vừa xong nhân với \(k\). - Chữ cái: thêm vào tầng hiện tại.
ngan_xep = []
hien_tai = []
so = 0
for ch in cong_thuc:
if ch.isdigit():
so = so * 10 + int(ch)
elif ch == "[":
ngan_xep.append((hien_tai, so))
hien_tai, so = [], 0
elif ch == "]":
trong = "".join(hien_tai)
hien_tai, k = ngan_xep.pop()
hien_tai.append(trong * k)
else:
hien_tai.append(ch)
Hai chi tiết quan trọng về tốc độ:
- Dùng phép nhân chuỗi
trong * k, không viết vòngforlặp \(k\) lần. Với1000000000[], phép nhân"" * 10**9cho kết quả ngay lập tức, còn vòng lặp một tỉ lần thì TLE. - Lưu mỗi tầng là một
listcác mảnh chuỗi, cuối cùng mới"".join(...). Cộng chuỗi liên tục bằng+=vẫn chạy được với dữ liệu bài này, nhưng dùnglist+joinlà thói quen tốt hơn.
Độ phức tạp
Mỗi ký tự của công thức được xử lý một lần. Phần tốn thời gian nhất là sao chép chuỗi khi join và nhân chuỗi, tổng cộng tỉ lệ với (độ sâu lồng nhau) × (độ dài kết quả) trong trường hợp xấu nhất, vẫn chạy nhanh với giới hạn của đề.
Code mẫu
def khai_trien(cong_thuc):
ngan_xep = []
hien_tai = []
so = 0
for ch in cong_thuc:
if ch.isdigit():
so = so * 10 + int(ch)
elif ch == "[":
ngan_xep.append((hien_tai, so))
hien_tai, so = [], 0
elif ch == "]":
trong = "".join(hien_tai)
hien_tai, k = ngan_xep.pop()
hien_tai.append(trong * k)
else:
hien_tai.append(ch)
return "".join(hien_tai)
print(khai_trien(input().strip()))
Comments