მიმდევრობის ბალანსირება

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მოცემულია მრგვალი ფრჩხილებისაგან შედგენილი მიმდევრობა. გამოთვალეთ სიმბოლოების მინიმალური რაოდენობა, რომელთა ინვერტაციის შედეგად მიმდევრობა ბალანსირებული გახდება. ინვერტაცია გულისხმობს მარცხენა ფრჩხილის შეცვლას მარჯვენათი და პირიქით.

ფრჩხილთა მიმდევრობის ბალანსირებულობის განსაზღვრისათვის რამდენიმე სხვადასხვა გზა არსებობს. მათგან ყველაზე მარტივი არის ის, რომ მარჯვენა და მარცხენა ფრჩხილების რაოდენობები სტრიქონში ტოლია და სტრიქონში ნებისმიერი პრეფიქსისათვის მარჯვენა ფრჩხილების რაოდენობა არ აღემატება მარცხენა ფრჩხილების რაოდენობას. მაგალითად, შემდეგი სტრიქონები ბალანსირებულია:

()

(())

()(()())

შემდეგი სტრიქონები კი არ არის ბალანსირებული:

)(

())(

((())))

შეტანის ფორმატი: * სტრიქონი 1: ფრჩხილებისაგან შედგენილი სტრიქონის სიგრძე არ აღემატება 100,000-ს.

გამოტანის ფორმატი: * სტრიქონი 1: ერთადერთი მთელი რიცხვი - იმ ფრჩხილების მინიმალური რაოდენობა, რომელთა ინვერტაცია (საპირისპიროთი შეცვლა) საჭიროა ბალანსირებული სტრიქონის მისაღებად.




მაგალითები

შესატანი მონაცემები
())( დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

გამოტანის განმარტება: მეოთხე ფრჩხილის შეცვლა აუცილებელია. ასევე საჭიროა შეიცვალოს მეორე და მესამე ფრჩხილებიდან ერთ-ერთი.