Alice tìm ra thuật toán riêng để nén một chuỗi yêu thích ~T~ chỉ bao gồm các chữ cái viết thường của bảng chữ cái tiếng Anh viết liên tiếp nhau. Chuỗi sau khi nén, ký hiệu là ~S~, có thể bao gồm các số, các chữ cái viết thường của bảng chữ cái tiếng Anh, các ký tự ~*~, các dấu ngoặc vuông "~[~" và "~]~", và các dấu ngoặc tròn "~(~" và "~)~".
Bob với bản tính tò mò muốn khám phá ra thuật toán và cố gắng giải nén chuỗi ~S~ bằng cách thực hiện các phép biến đổi lặp đi lặp lại. Một phép biến đổi có thể thuộc một trong ~3~ dạng dưới đây, trong đó chuỗi ~S~ chỉ gồm các chữ cái được ký hiệu là ~C~:
Chuỗi ~S~ có dạng ~n(C)~, trong đó ~n~ là số tự nhiên nằm ngay trước dấu ngoặc tròn, được biến đổi thành chuỗi ~D~ thu được bằng cách lặp liên tiếp ~n~ lần chuỗi ~C~. Ví dụ, với chuỗi ~5(ab)~ ta có ~n = 5~ và thu được dãy ~D = ababababab~.
Chuỗi ~S~ có dạng ~[∗C]~ được biến đổi thành một chuỗi palindrom (nghĩa là chuỗi đối xứng) có độ dài chẵn, thu được bằng cách ghép chuỗi ~C~ với chuỗi ngược của ~C~. Ví dụ, với chuỗi ~[∗abc]~, chuỗi palindrom thu được có độ dài chẵn là ~abccba~.
Chuỗi ~S~ có dạng ~[C∗]~ được biến đổi thành một chuỗi palindrom có độ dài lẻ, thu được bằng cách ghép dãy ~C~ với chuỗi ngược của ~C~ mà bỏ đi ký tự đầu tiên. Ví dụ, với chuỗi ~[abc∗]~, chuỗi palindrom thu được có độ dài lẻ là ~abcba~.
Một chuỗi được coi là đã được giải nén nếu nó chỉ bao gồm các chữ cái viết thường của bảng chữ cái tiếng Anh.
Yêu cầu
Cho chuỗi đã nén ~S~, hãy giúp Bob xác định số lần biến đổi thuộc ~3~ kiểu trên, cùng với chuỗi ~T~ ban đầu trước khi nén của chuỗi ~S~.
Dữ liệu vào
Một dòng duy nhất chứa chuỗi ~S~, các kí tự viết liền nhau.
Kết quả
Dòng đầu tiên chứa một số nguyên là số phép biến đổi tìm được. Dòng thứ hai chứa chuỗi ~T~ tìm được.
Sample Input 1
2(a)[*a2(b)]xy[2(c)b*]d
Sample Output 1
5
aaabbbbaxyccbccd
Giải thích 1
2(a) => aa
2(b) => bb
[*a2(b)] => [*abb] => abbbba
2(c) => cc
[2(c)b*] => [ccb*] => ccbcc
Sample Input 2
2(ab[cd*])a3(xyz)
Sample Output 2
3
abcdcabcdcaxyzxyzxyz
Giải thích 2
3(xyz) => xyzxyzxyz
[cd*] => cdc
2(ab[cd*]) => 2(abcdc) => abcdcabcdc
Sample Input 3
abcd
Sample Output 3
0
abcd
Giải thích 3
Không cần biến đổi vì chuỗi ban đầu T giống hệt với chuỗi nén S.
Hạn chế
- ~0 < |S| ≤ 10000; 0 < |T| ≤ 100000; ~
- ~1 < n ≤ 1000;~
- Dữ liệu đảm bảo các xâu đầu vào đúng format nằm trong ba dạng mô tả ở trên và không có dạng [*S*];
- Có ~30~% tổng số điểm của bài ứng với các bộ test mà chỉ có thể dùng phép biến đổi loại ~1~;
- Có ~30~% tổng số điểm của bài ứng với các bộ test khác mà chỉ có thể dùng phép biến đổi loại ~2~ hoặc loại ~3~. *
Nguồn: Trại đông Bảo Lộc 2021 - thầy Đỗ Phan Thuận
Bình luận