DAYNGO3 - Dãy ngoặc 3
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Bạn Nam là người yêu thích dấu mở ngoặc '(' hơn là dấu đóng ngoặc ')'. Với một dãy ngoặc bất kỳ, giả sử A là số lượng dấu mở ngoặc và B là số lượng dấu đóng ngoặc, nếu A > B thì Nam gán cho dãy ngoặc đó một độ yêu thích là Y = A - B. Nếu A ≤ B thì độ yêu thích Y = 0.

Giả sử Nam có một dãy ngoặc S bất kỳ gồm hai dấu mở ngoặc và đóng ngoặc, S có chiều dài là n. Bây giờ Nam muốn tính tổng độ yêu thích của tất cả các dãy ngoặc con của dãy S, bạn hãy giúp Nam nhé (dãy ngoặc con là dãy bắt đầu từ vị trí p và kết thúc tại vị trí r, với 1 ≤ p ≤ r ≤ n)

Dữ liệu nhập:

- Dòng đầu tiên là số nguyên n, chiều dài của dãy S (1 ≤ n ≤ 105)

- Dòng thứ hai là n ký tự của dãy S

Dữ liệu xuất:

- Là số nguyên xác định tổng độ yêu thích của tất cả các dãy ngoặc con của S.

Ví dụ

  • input
    4
    (())
    output
    5
  • input
    4
    ((((
    output
    20

Test 1 có 04 dãy ngoặc con độ yêu thích > 0 như sau:

(: Y=1

(: Y=1

((: Y=2

((): Y=1

Tổng cộng độ yêu thích là 5.

 

Back to Top