Time Limit: 2 sec / Memory Limit: 256 MB
問題
♪「ガラガラガラ~、レアカード来い!」 俺は今、巷で人気のソーシャルカードゲームにはまっている。 このゲームは「カードローダー」という名のガチャシステムで カードを増やし、カード合成でデッキ(手札)を強化して コンピュータや他のプレーヤーと対戦するといったゲームである。 巷によくあるゲーム形式で、課金しないとなかなか楽しめないと いうところも定番通りである。 たった今カードローダーで 引いたカード「のろのろウサギ*(N)」(名前の後ろの括弧は希少価値を表す) は戦闘力最弱の屑カードである。 いつになったら 目的のレアカードが出現してくれるのだろうか。
俺は貧乏ゲーマーなので課金はしたくない。 しかし、 ゲームヒロイン「アリシア」のレアカードが欲しくてたまらない。 そこで俺は友達に協力を依頼してカードローダーについて調査を行った。 残念なことに、カードローダーで得られるカードは10枚目ごとにかつそのときに限り必ず「のろのろウサギ*(N)」であることしか分からなかった。
そうこうしている内にゲーム主催者の方から特別なイベントの告知が行われた。 イベントは数種類あるカードローダーで入手可能なカードの種類と 入手確率が公開されるというもので、 「プレーヤーの皆様の日頃のご愛顧に感謝し、レアカードを椀飯振舞することに いたしました。奮ってご参加ください。」とのことだ。 イベント詳細を詳しく見ると、今までとカードローダーの仕組みは変わらず、 入手できるカードの入れ替えと入手確率を変更し、 いつもよりレアカードが入手しやすくなっているらしい。
いてもたってもいられず、いざカードローダーと思ったとき、ふと思った。 「いくらいつもより確率が良くても、いったい何回カードローダーを動かせば アリシアちゃんのカードが入手できるのだろう」と。 俺は金がない代わりにゲームする時間はある、けれどこの手のゲームの定番で 課金しない状況では続けて何回も動かすことはできない。 何回動かせば入手できるか知ることが出来れば、実際いつ頃入手できるか 推測がたつ。 もし、来週の今頃であるなら、今週はとてもウキウキした 一週間になるに違いない。 もし、1ヶ月先であるならば、 カードを入手する前にイベントが終了しているかもしれない。 「あ~、神よ。俺にレアカードをお恵くださいorz」
あなたの仕事はカードの入手確率とカードローダーの動作回数をもとに「俺」が入手できるアリシアのレアカードの枚数の期待値を求めることである。
ここでいうレアカードとは、N(ノーマル), R(レア), S(スーパーレア), H(ハイパーレア)の 4種類の希少価値がある中で、R,S,Hの3種類いずれかの希少価値をもつカードを指す。
入力
N T card\_name_1 rarity_1 rate_1 : card\_name_N rarity_N rate_N
- 1行目には整数 N, T が与えられます。
- N は出現率について得られた情報の数を表します。
- 1 ≦ N ≦ 10,000 であることは保証されています。
- Tは試行回数を表します。
- 0 ≦ T ≦ 100,000,000 であることは保証されています。
- 2 行目から N + 1 行目までの N 行では、カード名称、希少価値および出現頻度がそれぞれ半角スペース区切りで与えられます。
- card\_name_i は i 枚目のカード名称を表します。
- card\_name_i は半角英数字の他に
[
,]
,&
,!
,?
,+
,-
,_
,/
によって構成されます。 - card\_name_i は 1 文字以上 20 文字以下であることが保証されています。
- アリシアのカードである場合、card\_name_i に “Alicia” の文字列を含みます。例えば「アリシア[ひとやすみ]」は「Alicia[hitoyasumi]」となります。
- rarity_i は i 枚目のカードの希少価値を表します。
- rarity_i は
N
,R
,S
,H
のいずれかであることが保証されています。 - rate_i は出現頻度を表します。
- 1 ≦ rate_i ≦ 100,000 であることは保証されています。
- カードローダーは指定された確率を用いるとき、 rate_i / (rate_1 + … + rate_N) の確率で i 番目のカードを生成します。
出力
入力例
3 3 Alicia[Normal] N 40 Superheroine_Alicia R 9 Secret_of_Alicia H 1
出力例
0.6