No.22 Bracket Matching
タグ : / 解いたユーザー数 823
作問者 :
yuki2006
Problem Statement
Orino wants to write a program that finds the matching positions of brackets in a text.
Bracket matching is defined as follows:
1. If the given string contains a "(" immediately followed by a ")", delete those two characters from the string.
2. Taking the string after the deletion as the new string, repeat the process of 1. until the string becomes empty.
Then, in terms of positions in the initially given string, the \(i\)-th character and the $j$-th character deleted together with it are said to be a "bracket match".
You are given a string of \(N\) characters consisting only of "(" and ")",
and also an integer \(K\ (1 \leq K \leq N)\).
Find the position of the character that matches the \(K\)-th character.
It is guaranteed that every character in the given string has a bracket match.
Input
N K S
Line \(1\) contains \(N\ (1 \leq N \leq 10000)\), the number of characters, and \(K\ (1 \leq K \leq N)\), the index of the specified character, separated by a space.
Line \(2\) contains the string representing the actual characters. It is guaranteed that this string consists of "(" or ")".
Output
Output the integer answer, including the trailing newline.
Print a newline at the end.
Sample
Sample 1
Input
4 4 (())
Output
1
The \(4\)-th character of "(())" is ")". The character matching it is the "(" at position \(1\).
Sample 2
Input
12 2 (((())()()))
Output
11
The \(2\)-th character of the string "(((())()())) " is "(". The character matching it is the ")" at position \(11\).
Sample 3
Input
20 5 ((((((()))))))(()())
Output
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。