No.78 クジ付きアイスバー
nmnmnmnmnmnmnm問題文
A君は当たりクジ付きのアイスバーが大好きである。
アイスバーには「ハズレ」と「1本当たり」と「2本当たり」がある。
ハズレは何ももらえないが、当たりだとその本数をタダでもらえる。
お店ではアイスバーが箱詰めされて売られている。
1つの箱にはN本のアイスバーが入っている。
A君は箱の先頭から順にしかアイスバーを取り出すことはできない。
買う場合も当たりと引き換えの場合もこの箱からアイスバーを取り出す。
1つの箱の中のハズレと当たりクジの配置はどの箱も同じである。
お店には1つのアイスバーの箱があり、売り切れると1つの新しい箱を補充する。
いまお店には新しい手つかずのアイスバーの箱がある。
A君は最初は「当たり」クジを持っておらず予算は無限にある。
K本のアイスバーを食べるためにはA君は最低何本のアイスを買う必要があるか？
入力
N K S
$N$は1箱に入っているアイスバーの数。$1 \le N \le 50$。$N$は正の整数。
$K$はA君が食べる予定のアイスバーの数。$1 \le K \le2000000000=2 \cdot 10^9$。$K$は正の整数。
$S$の長さは$N$の値と等しい。
文字列Sは'0'と'1'と'2'の3種類の文字で構成される。
'0'は「ハズレ」、'1'は「1本当たり」、'2'は「2本当たり」をあらわす。
文字列の文字の順番に箱の先頭からアイスバーが入っていると考える。
出力
A君が買うアイスバーの本数を答えよ。
最後に改行を忘れずに。
サンプル
サンプル1
入力
5 4 01200
出力
2
1つの箱の中には5個のアイスバーが入っている。
先頭から順に「ハズレ」、「1本当たり」、「2本当たり」、「ハズレ」、「ハズレ」である。
最初の2本のアイスバーは購入しなければならない。
2本目のアイスバーは「1本当たり」であるので3本目のアイスバーはタダでもらえる。
3本目のアイスバーは「2本当たり」であるので4,5本目のアイスバーもタダでもらえる。
A君が食べたいアイスバーの数は4本なのでこの時点で目的は達成した。
A君が購入したアイスバーは2本である。
サンプル2
入力
2 8 10
出力
4
1つのアイスバーの箱に2本のアイスバーが入っている。
箱には「1本当たり」、「ハズレ」の順番でアイスバーが入っている。
1本買うたびに1本もらえるので1本買うと2本食べれると考える。
よって、8本食べるには4本の購入が必要となる。
サンプル3
入力
10 100 2222222222
出力
1
1つの箱に「2本当たり」のアイスバーが10本入っている。
当たりを使ってアイスバーをもらい放題だが最初の1本はどうしても買う必要がある。
サンプル4
入力
2 5 01
出力
3
1つのアイスバーの箱に2本のアイスバーが入っている。
箱には「ハズレ」、「1本当たり」の順番でアイスバーが入っている。
5本のアイスバーを食べるには3本のアイスバーの購入が必要である。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。