#1317. BRACKVAL - Giá trị biểu thức ngoặc

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Vũ Mạnh Hà - Ôn Hải Phòng 08/11/2020

Xét các dãy ngoặc đúng (chỉ gồm ′(' và ′)′). Người ta tính giá trị của một dãy ngoặc đúng theo qui tắc sau:

  • Giá trị của () là 1 ;
  • Nếu 𝐴 có giá trị 𝑥 thì (𝐴) có giá trị 2𝑥 ;
  • Nếu 𝐴, 𝐵 có giá trị 𝑥, 𝑦 thì 𝐴𝐵 có giá trị 𝑥 + 𝑦 ;

Chẳng hạn giá trị của ′(())()′ là 2 × 1 + 1 = 3 .

Cho một dãy ngoặc đúng độ dài 𝑁 . Hãy xác định giá trị của nó.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương 𝑁\ (2 ≤ 𝑁 ≤ 10^5) ;
  • N dòng tiếp theo, dòng thứ 𝑖 ghi số 0 nếu vị trí tương ứng là '(' và ghi số 1 nếu là ')';

Dữ liệu ra:

  • Một số nguyên duy nhất là kết quả tìm được, lấy phần dư khi chia cho 12345678910 .

Ví dụ:

Dữ liệu vào:
6
0
0
1
1
0
1
Dữ liệu ra:
3