Xâu con cân bằng

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một xâu nhị phân \(S\) chỉ gồm các ký tự '0' và '1' có độ dài \(N\). Một xâu con được gọi là "cân bằng" nếu số lượng ký tự '0' bằng số lượng ký tự '1' trong xâu con đó. Hãy đếm số lượng xâu con cân bằng của \(S\).

Input

Một dòng duy nhất chứa xâu nhị phân \(S\) (\(1 \le |S| \le 10^5\)).

Output

Một số nguyên duy nhất là số lượng xâu con cân bằng.

Example

Test 1

Input

Output

Note

Giải thích ví dụ 1 (0101): Các xâu con cân bằng là: "01" (vị trí 1-2), "10" (vị trí 2-3), "01" (vị trí 3-4), và "0101" (vị trí 1-4).

Test 2

Input

Output

Note

Giải thích ví dụ 2 (1100): Các xâu con cân bằng là: "10" (vị trí 2-3), "1100" (vị trí 1-4).

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(|S| \le 1000\).
Subtask \(2\) (\(60\%\) số điểm): \(|S| \le 10^5\).

Bình luận

Tải bình luận...

Không có bình luận nào.