No.22 括弧の対応

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 455
作問者 : yuki2006yuki2006
5 ProblemId : 68 / 出題時の順位表

問題文

Orinoは、テキストの括弧の対応箇所を見つけるプログラムを書きたいと思っている。

括弧の対応とは、

1.与えられた文字列から、「(」の直後に「)」が来る文字があるとき、文字列からその2つの文字を削除する。
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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。