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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้