1169 : เติมวงเล็บ
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

ให้สตริงที่ประกอบไปด้วยวงเล็บเปิด ‘(‘ และวงเล็บปิด ‘)’  จงคำนวณหาจำนวนวงเล็บเปิดหรือปิดที่น้อยที่สุดที่ต้องเติมในสตริงดังกล่าว เพื่อทำให้วงเล็บเปิดและปิดจับคู่กันได้อย่างถูกต้อง  (สำหรับนิยามอย่างเป็นทางการของการจับคู่ได้อย่างถูกต้องดูได้จากส่วนอธิบายเพิ่มเติมท้ายโจทย์)

                พิจารณาตัวอย่างตามตารางด้านล่าง

สตริงตั้งต้น

การเติมที่น้อยที่สุดแบบหนึ่ง

จำนวนที่ต้องเติม

(()(

(())()

2

())(

(())()

2

((())())

((())())

0

(()()))())

(()()())()()

2

งานของคุณ

เขียนโปรแกรมรับสตริงที่ประกอบด้วยวงเล็บเปิดและวง เล็บปิด จากนั้นคำนวณหาจำนวนวงเล็บที่ต้องเติมเข้าไปในสตริงดังกล่าว เพื่อให้เป็นสตริงที่วงเล็บเปิดและปิดจับคู่กันได้อย่างถูกต้อง

ข้อมูลนำเข้า

มีบรรทัดเดียวเป็นสตริงที่ประกอบด้วยวงเล็บเปิดและวงเล็บปิด ความยาวไม่เกิน 200 ตัวอักษร

ข้อมูลส่งออก

มีหนึ่งบรรทัด เป็นจำนวนเต็มแทนจำนวนวงเล็บที่น้อยที่สุดที่ต้องเติมเข้าไปในสตริงเพื่อให้เป็นสตริงที่ถูกต้อง

คำอธิบายเพิ่มเติม (ไม่จำเป็นนักต่อการทำโจทย์)

สำหรับสตริงที่ประกอบไปด้วยวงเล็บเปิดและวงเล็บปิด เราจะกล่าวว่าสตริงดังกล่าวมีการจับกันของวงเล็บเปิดและปิดอย่างถูกต้อง ก็ต่อเมื่อเราสามารถจับคู่วงเล็บเปิดกับวงเล็บปิดได้แบบ 1 ต่อ 1 โดยที่สอดคล้องกับเงื่อนไขต่อไปนี้:  ถ้าวงเล็บเปิดที่เป็นอักขระที่ i จับคู่กับวงเล็บปิดที่เป็นอักขระที่ j ในสตริง เราจะได้ว่า

·        i < j   (วงเล็บเปิดอยู่หน้าวงเล็บปิด),

·        สำหรับวงเล็บเปิดใด ๆ ที่อยู่ที่ตำแหน่ง a ที่ i < a < j, วงเล็บเปิดนั้นจะต้องจับคู่กับวงเล็บปิดที่อยู่ที่ตำแหน่ง b ที่ a < b < j เท่านั้น

·        และในทางกลับกัน วงเล็บปิดใด ๆ ที่อยู่ที่ตำแหน่ง a ที่ i < a < j, วงเล็บปิดนั้นจะต้องจับคู่กับวงเล็บเปิดที่อยู่ที่ตำแหน่ง b ที่ i < b < a เท่านั้น เช่นกัน

ที่มา : IOI Thailand League 2010 เดือนพฤษภาคม




ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
())( 2
(()()))()) 2

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 5 สมาชิก (2 บอท)