No.22 括弧の対応
yuki2006問題文
Orinoは、テキストの括弧の対応箇所を見つけるプログラムを書きたいと思っている。
括弧の対応とは、
1.与えられた文字列から、「(」の直後に「)」が来る文字があるとき、文字列からその２つの文字を削除する。
2.削除された文字を新たな文字列として、1.の処理を繰り返し、文字列が空になるまで繰り返す。
そして、初めに与えられた文字列として考えた時の\(i\)番目文字と一緒に削除される$j$番目に対応する文字が「括弧の対応」であるとする。
「(」と「)」のみで構成される\(N\)文字の文字列が与えられ、
さらに整数値\(K\ (1 \leq K \leq N)\)が与えられる。
このとき、\(K\)番目の文字と対応する文字の箇所の番目を求めてください。
与えられる文字列は、すべての文字で括弧の対応があると保証されるとする。
入力
N K S
\(1\)行目は 文字数を表す\(N\ (1 \leq N \leq 10000)\)と、指定された文字の番号\(K\ (1 \leq K \leq N)\)がスペース区切りで与えられる。
\(2\)行目は、実際の文字を表す文字列が与えられる。この文字列は「(」または「)」であることが保証される。
出力
答えの整数値を最後の改行を含め出力してください。
最後に改行してください。
サンプル
サンプル1
入力
4 4 (())
出力
1
「(())」の文字の\(4\)番目は、「)」である、このとき対応する文字は\(1\)番目の「(」である。
サンプル2
入力
12 2 (((())()()))
出力
11
「(((())()())) 」という文字列の \(2\)番目の文字は「(」である。このとき対応する文字は\(11\)番目の「)」である。
サンプル3
入力
20 5 ((((((()))))))(()())
出力
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。