No.78 クジ付きアイスバー

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 88
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

6 ProblemId : 152 / 出題時の順位表

問題文

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本のアイスバーの購入が必要である。

提出ページヘ