تحاول Bessie كتابة سلسلة أقواس متوازنة على حاسوبها المحمول الجديد، لكن حوافرها الكبيرة تجعلها خرقاء وتخطئ في الأحرف. أوجد أقل عدد أحرف يجب قلبها (فتح إلى إغلاق أو العكس) لتصبح السلسلة متوازنة.
للتوازن عدة تعريفات. أبسطها تساوي مجموع أقواس الفتح والإغلاق، وفي كل بادئة يوجد من أقواس الفتح ما لا يقل عن الإغلاق. السلاسل التالية متوازنة:
() (()) ()(()())
وهذه غير متوازنة:
)( ())( ((())))
الإدخال
- السطر 1: سلسلة أقواس $A$ بطول زوجي لا يتجاوز 100,000 رمز.
الإخراج
- السطر 1: عدد صحيح، أقل عدد أقواس يجب قلبها لتوازن السلسلة.
أمثلة
الإدخال 1
())(
الإخراج 1
2
ملاحظة
يجب قلب القوس الأخير وأحد قوسي الإغلاق في الوسط.
مؤلف المسألة: Brian Dean، 2012