Poker

题目描述

我们有 $9K$ 张牌。对于每个 $i = 1, 2, \dots, 9$，有 $K$ 张写着数字 $i$ 的牌。
我们随机洗牌并发给高桥和青木每人五张牌 —— 四张明面朝上和一张背面朝下。
给你一个字符串 $S$ 表示发给高桥的牌，和一个字符串 $T$ 表示发给青木的牌。
$S$ 和 $T$ 是长度为五的字符串。每个字符串的前四个字符是 $1$、$2$、$\dots$ 或 $9$，表示明面朝上的牌上的数字。每个字符串的最后一个字符是 #，表示该牌是背面朝下的。
我们将五张牌的手牌得分定义为 $\displaystyle \sum_{i=1}^9 i \times 10^{c_i}$，其中 $c_i$ 是写着数字 $i$ 的牌的张数。
当高桥的手牌得分大于青木的手牌得分时，高桥获胜。
求高桥获胜的概率。

输入格式

输入按下述格式从标准输入给出： $K$ $S$ $T$

输出格式

输出高桥获胜的概率，格式为十进制小数。 当你的答案与我们的答案的绝对或相对误差至多 $10^{-5}$ 时，将判定为正确。

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$, $2$, $\dots$, 或 $9$。 每个数字 $1, 2, \dots, 9$ 在 $S$ 和 $T$ 中总共出现的次数至多为 $K$。 $S$ 和 $T$ 的第五个字符均为 #。例如，如果高桥的手牌是 $11449$ 而青木的手牌是 $22338$，高桥的得分是 $100+2+3+400+5+6+7+8+90=621$，青木的得分是 $1+200+300+4+5+6+7+80+9=612$，因此高桥获胜。
当高桥背面朝下的牌上的数字大于青木背面朝下的牌上的数字时高桥获胜，所以高桥获胜的概率为 $\frac49$.
高桥仅在高桥的手牌为 $11222$ 且青木的手牌为 $22281$ 时获胜，概率为 $\frac2{1035}$。

标签: AtCoder|abc193D

来源

AtCoder|abc193D