Giống bò cân bằng (Dễ)

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho chuỗi $N$ dấu ngoặc. Gán mỗi ký tự cho một trong hai giống bò (H hoặc G). Đếm số cách gán sao cho chuỗi con của giống H và chuỗi con của giống G đều là chuỗi ngoặc hợp lệ. Kết quả lấy modulo $2012$ .

Chuỗi ngoặc hợp lệ: số ( bằng số ), và mọi tiền tố đều có số ( $\geq$ số ).

Dữ liệu vào

Một dòng chứa chuỗi dấu ngoặc độ dài $N$ .

Dữ liệu ra

Một số nguyên — số cách gán modulo $2012$ .

Ràng buộc

$1 \leq N \leq 1000$

Ví dụ

Input	Output	Giải thích
(())	6	6 cách gán hợp lệ: HHHH, GGGG, HGGH, GHHG, HGHG, GHGH.

Bình luận

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