Xâu Ami

View as PDF

Points: 100 Time limit: 2.0s Memory limit: 256M Input: stdin Output: stdout

Xâu kí tự ami được định nghĩa đệ quy như sau:

  • Xâu rỗng là một xâu ami.
  • Nếu \(A\)\(B\) là các xâu ami thì một xâu mới \(C\) được tạo ra bằng cách ghép hai xâu này với nhau cũng là một xâu ami (AB và BA là xâu ami).
  • Nếu \(A\) là một xâu ami thì một xâu mới \(C\) được tạo ra bằng cách thêm vào vị trí đầu và cuối của \(A\) cùng một kí tự \(x\) cũng là một xâu ami (xAx là một xâu ami).

Ví dụ, một số xâu ami\(aabb\), \(abccba\). Các xâu \(ami\), \(cuom\) không phải là xâu ami.

Các bạn có một xâu \(S\) chỉ gồm các kí tự tiếng Anh thường. Hãy xác định xem đây có phải là một xâu ami hay không.

Input

  • Một dòng chứa xâu kí tự \(S\).

Output

  • Hãy in ra 1 nếu xâu \(S\) là xâu ami và in ra 0 trong trường hợp ngược lại.

Scoring

Gọi \(n\) là độ dài xâu \(S\).

  • Subtask \(1\) (\(60\%\) số điểm): \(1 \le n \le 100\).
  • Subtask \(2\) (\(10\%\) số điểm): \(1 \le n \le 1000\).
  • Subtask \(3\) (\(30\%\) số điểm): \(1 \le n \le 10^5\).

Example

Test 1

Input
caabbc
Output
1
Note

Xâu \(aa\)\(bb\) là các xâu ami. Do đó, ghép hai xâu này lại, ta được xâu \(aabb\) là xâu ami. Xâu \(aabb\) là xâu ami, vậy thêm kí tự \(c\) vào đầu và cuối xầu này, ta được xâu \(caabbc\) là xâu ami.

Test 2

Input
caabbcd
Output
0

Comments

There are no comments at the moment.