Rút gọn xâu
Xem PDF
Điểm:
200
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho xâu nhị phân \(s\) gồm \(n\) phần tử và một phép rút gọn xâu như sau:
- Chọn \(2\) phần tử kề nhau và khác nhau, sau đó xoá chúng đi.
Ta thực hiện phép toán này với số lần bất kì cho đến khi xâu \(s\) không thể rút gọn được nữa thì thôi.
Hỏi độ dài xâu \(s\) tối thiểu sau khi rút gọn là bao nhiêu ?
Input
-
Dòng thứ nhất chứa số \(n\) thể hiện độ dài của xâu \((1\le n\le 200000)\)
-
Dòng thứ hai chứa xâu \(s\) có độ dài \(n\)
Output
- In ra độ dài xâu \(s\) tối thiểu sau khi đã rút gọn
Example
Test 1
Input
6
011100 Output
0Note
-
Giả sử ta đánh chỉ số bắt đầu từ 1, thì phép rút gọn xâu được thực hiện như sau:
-
Bước 1: Ta xoá đi hai phần tử \(1\) và \(2\). Xâu \(s\) còn lại là: \(1100\)
-
Bước 2: Ta xoá đi hai phần tử \(2\) và \(3\). Xâu \(s\) còn lại là: \(10\)
-
Bước 3: Ta xoá đi hai phần tử \(1\) và \(2\). Ta được xâu $s $rỗng.
Do đó độ dài xâu \(s\) là \(0\)
Bình luận