题目描述

$1,\ 2,\ \dots,\ 9$ が表に書かれたカードが $K$ 枚ずつ、計 $9K$ 枚のカードがあります。
これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、$4$ 枚を表向きに、$1$ 枚を裏向きにして配りました。
高橋くんに配られたカードが文字列 $S$ として、青木くんに配られたカードが文字列 $T$ として与えられます。
$S,\ T$ は $5$ 文字の文字列で、先頭 $4$ 文字は 1, 2, $\dots$, 9 からなり、表向きのカードに書かれた数を表します。 末尾 $1$ 文字は # であり、裏向きのカードであることを表します。
$5$ 枚の手札の点数を、$c_i$ をその手札に含まれる $i$ の枚数として、$\displaystyle\ \sum_{i=1}^9\ i\ \times\ 10^{c_i}$ で定義します。
高橋くんが青木くんより点数の高い手札を持っていたら高橋くんの勝ちです。
高橋くんの勝つ確率を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$K$ $S$ $T$

输出格式

高橋くんの勝つ確率を小数で出力せよ。
想定解答との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解と判定される。

题目大意

题意：

有 $9K$ 张卡片，每张卡片上写有 $1,2,\dots,9$ 中的一个数。这些卡片被随机洗牌，然后将其中 $4K$ 张正面朝上，$K$ 张背面朝上的卡片分别发给高桥和青木。高桥获得的卡片用字符串 $S$ 表示，青木获得的卡片用字符串 $T$ 表示。

字符串 $S$ 和 $T$ 是长度为 $5K$ 的字符串，其中前 $4K$ 个字符是 $1,2,\dots,9$ 中的某一个数字，表示正面朝上的卡片上的数字。接下来的 $1K$ 个字符是 #，表示背面朝上的卡片。定义一组牌的得分为其中包含 $i$ 张数字 $i$ 的牌的数量乘以 $10^i$ 的和，即：

其中 $c_i$ 是字符串 $S$ 或 $T$ 中数字 $i$ 出现的次数。如果高桥的得分比青木高，则高桥获胜。请计算高桥获胜的概率。

2
1144#
2233#

0.4444444444444444

2
9988#
1122#

1.0

6
1122#
2228#

0.001932367149758454

100000
3226#
3597#

0.6296297942426154

提示

制約

• $2\ <\ = K\ <\ =\ 10^5$
• $|S|\ =\ |T|\ =\ 5$
• $S,\ T$ の $1$ 文字目から $4$ 文字目は 1, 2, $\dots$, 9 のいずれか
• 1, 2, $\dots$, 9 はそれぞれ、$S$ と $T$ に合計 $K$ 回までしか出現しない
• $S,\ T$ の $5$ 文字目は #

Sample Explanation 1

例えば、高橋くんの手札が 11449 、青木くんの手札が 22338 の場合、高橋くんの点数は $100+2+3+400+5+6+7+8+90=621$ 、青木くんの点数は $1+200+300+4+5+6+7+80+9=612$ で、高橋くんの勝ちになります。 裏向きのカードの大小によって勝敗が決まるので、高橋くんの勝つ確率は $\frac49$ です。

Sample Explanation 3

高橋くんの手札が 11222 、青木くんの手札が 22281 の場合にのみ高橋くんの勝ちになります。 高橋くんの勝つ確率は $\frac2{1035}$ です。