Dãy ngoặc

Điểm: 7,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Một dãy ngoặc hợp lệ là một xâu ký tự gồm các ký tự $($ , $)$ , $[$ , $]$ , ${$ , $}$ thỏa mãn:

Xâu rỗng là dãy ngoặc hợp lệ.
Nếu $A$ là dãy ngoặc hợp lệ thì $(A)$ , $[A]$ , ${A}$ cũng là dãy ngoặc hợp lệ.
Nếu $A$ và $B$ là các dãy ngoặc hợp lệ thì $A B$ cũng là dãy ngoặc hợp lệ.

Độ sâu lồng nhau của một dãy ngoặc hợp lệ là số lượng cặp ngoặc lồng nhau nhiều nhất tại bất kỳ vị trí nào trong xâu.

Xét tất cả các dãy ngoặc hợp lệ có độ dài $n$ và độ sâu lồng nhau không quá $k$ . Sắp xếp các dãy này theo thứ tự từ điển với quy ước: $($ $<$ $)$ $<$ $[$ $<$ $]$ $<$ ${$ $<$ $}$ .

Yêu cầu: Cho một dãy ngoặc hợp lệ $S$ có độ dài $n$ và độ sâu lồng nhau không quá $k$ , hãy tìm thứ hạng của $S$ trong danh sách trên (đánh số từ $1$ ).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $n$ và $k$ .
Dòng thứ hai chứa xâu $S$ có độ dài $n$ .

Dữ liệu ra

Ghi ra một số nguyên duy nhất là thứ hạng của xâu $S$ .

Ví dụ

Input	Output	Giải thích
4 2 ()()	1	$" () () "$ là dãy ngoặc hợp lệ nhỏ nhất theo thứ tự từ điển có độ dài $4$ và độ sâu không quá $2$ .
4 2 (())	2	$" (()) "$ đứng thứ $2$ sau $" () () "$ .
2 1 []	2	Các dãy hợp lệ độ dài $2$ , độ sâu $\leq 1$ : $" () "$ , $" [] "$ , $" {} "$ . Xâu $" [] "$ đứng thứ $2$ .

Bình luận

Không có bình luận tại thời điểm này.