Points:
100
Time limit:
2.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Xâu kí tự
được định nghĩa đệ quy như sau:- Xâu rỗng là một xâu .
- Nếu \(A\) và \(B\) là các xâu 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 (AB và BA là xâu ).
- Nếu \(A\) là một xâu 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 (xAx là một xâu ).
Ví dụ, một số xâu \(aabb\), \(abccba\). Các xâu \(ami\), \(cuom\) không phải là xâu .
là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 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 và in ra0
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\) và \(bb\) là các xâu . Do đó, ghép hai xâu này lại, ta được xâu \(aabb\) là xâu . Xâu \(aabb\) là xâu , 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 .
Test 2
Input
caabbcd
Output
0
Comments