Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

STRBALAN - Chuỗi cân bằng

 

Bessie vừa mới mua một máy tính xách tay mới, nhưng cô ta lại không gõ bàn phím được cho tốt lắm vì móng chân lớn của cô ta so với kích thước nhỏ của bàn phím. Bessie vừa nhập vào bàn phím một dãy kí tự ưa thích của cô ta – một chuỗi ngoặc cân bằng. Tuy nhiên, cô ta nhận ra rằng cô ta có lẽ đã gõ nhầm một kí tự một cách vô tình, từ dấu mở ngoặc đơn thành dấu đóng ngoặc đơn, hoặc ngược lại. Hãy giúp Bessie đếm số vị trí trong chuỗi để nếu ta đổi ngược dấu ở vị trí đó thì chuỗi ban đầu sẽ thành chuỗi cân bằng.
Có nhiều cách để định nghĩa một chuỗi ngoặc là “cân bằng.” Cách dễ nhất là số lượng dấu mở ngoặc ‘(‘ bằng số lượng dấu đóng ngoặc ‘)’, và với bất kì chuỗi tiền tố nào, số lượng dấu mở ngoặc đơn ‘(‘ phải lớn hơn hoặc bằng số lượng dấu đóng ngoặc đơn ‘)’. Trong những ví dụ sau đây, những chuỗi ở bên dưới là chuỗi cân bằng:
()
(())
()(()())
Những chuỗi sau đây là chuỗi không cân bằng:
)(
())(
((())))

 

Bessie vừa mới mua một máy tính xách tay mới, nhưng cô ta lại không gõ bàn phím được cho tốt lắm vì móng chân lớn của cô ta so với kích thước nhỏ của bàn phím. Bessie vừa nhập vào bàn phím một dãy kí tự ưa thích của cô ta – một chuỗi ngoặc cân bằng. Tuy nhiên, cô ta nhận ra rằng cô ta có lẽ đã gõ nhầm một kí tự một cách vô tình, từ dấu mở ngoặc đơn thành dấu đóng ngoặc đơn, hoặc ngược lại. Hãy giúp Bessie đếm số vị trí trong chuỗi để nếu ta đổi ngược dấu ở vị trí đó thì chuỗi ban đầu sẽ thành chuỗi cân bằng.

Có nhiều cách để định nghĩa một chuỗi ngoặc là “cân bằng.” Cách dễ nhất là số lượng dấu mở ngoặc ‘(‘ bằng số lượng dấu đóng ngoặc ‘)’, và với bất kì chuỗi tiền tố nào, số lượng dấu mở ngoặc đơn ‘(‘ phải lớn hơn hoặc bằng số lượng dấu đóng ngoặc đơn ‘)’. Trong những ví dụ sau đây, những chuỗi ở bên dưới là chuỗi cân bằng:

()

(())

()(()())

Những chuỗi sau đây là chuỗi không cân bằng:

)(

())(

((())))

Input

Dòng 1: Một chuỗi ngoặc đơn có độ dài là N (1 <= N <= 100,000).

Output

Dòng 1: Số vị trí trong chuỗi ban đầu mà nếu ta đổi ngược dấu ở vị trí đó thì chuỗi sẽ thành chuỗi cân bằng.

Example

Input:
()(())))

Output:
4
Nếu ta nhìn cụ thể vào chuỗi ban đầu:
12345678
()(())))
Nếu ta đổi ngược dấu của kí tự thứ 2 thì chuỗi sẽ thành chuỗi cân bằng:
12345678
(((())))
Tương tự nếu ta đổi ở vị trí thứ 5,6, và 7, ta đều có kết quả là chuỗi cân bằng.
Submit solution!
Được gửi lên bởi:adm
Ngày:2013-01-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
hide comments
2018-05-14 05:20:20 Vu Duy Truc
Done!
Cùng thảo luận thêm với mình nhé.
https://goo.gl/forms/T9Bi45SMU7XWnkos1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.