E - Alicia's Rare card Challenge

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. 1行目には整数 N, T が与えられます。
    • N は出現率について得られた情報の数を表します。
    • 1 ≦ N ≦ 10,000 であることは保証されています。
    • Tは試行回数を表します。
    • 0 ≦ T ≦ 100,000,000 であることは保証されています。
  2. 2 行目から N + 1 行目までの N 行では、カード名称、希少価値および出現頻度がそれぞれ半角スペース区切りで与えられます。
    • card\_name_ii 枚目のカード名称を表します。
    • card\_name_i は半角英数字の他に [, ], &, !, ?, +, -, _, / によって構成されます。
    • card\_name_i は 1 文字以上 20 文字以下であることが保証されています。
    • アリシアのカードである場合、card\_name_i に “Alicia” の文字列を含みます。例えば「アリシア[ひとやすみ]」は「Alicia[hitoyasumi]」となります。
    • rarity_ii 枚目のカードの希少価値を表します。
    • rarity_iN, R, S, H のいずれかであることが保証されています。
    • rate_i は出現頻度を表します。
    • 1 ≦ rate_i ≦ 100,000 であることは保証されています。
    • カードローダーは指定された確率を用いるとき、 rate_i / (rate_1 + … + rate_N) の確率で i 番目のカードを生成します。

出力

アリシアのレアカードの入手枚数の期待値を 1 行に出力せよ。 出力は 10^{-6} 未満の誤差を含んでも良い。

入力例

3 3
Alicia[Normal] N 40
Superheroine_Alicia R 9
Secret_of_Alicia H 1

出力例

0.6

Source Name

Maximum-Cup 2013