分数: 400 点
问题陈述
我们有 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 。
当高桥牌的分数高于青木牌的分数时,高桥获胜。
求高桥获胜的概率。
约束
- 2 ≤ K ≤ 10^5
- |S| = |T| = 5
- 每个的第一个到第四个字符 S 和 T 是
1,2, \dots,或9. - 每个数字
最多出现
1,2, \dots,和9总共 K 次 S 和 T. - 每个的第五个字符 S 和 T is
#.
输入
输入由标准输入按以下格式给出:
K S T
输出
以小数形式打印高桥获胜的概率。 当您的答案与我们的答案的绝对或相对误差最多为 10^{-5}.
示例输入 1
2 1144# 2233#
示例输出 1
0.4444444444444444
例如,如果高桥的牌是 11449 青木的手是 22338,高桥的得分是 100+2+3+400+5+6+7+8+90=621 青木的分数是 1+200+300+4+5+6+7+80+9=612,导致高桥获胜。
当高桥面朝下的牌上的数字大于青木面朝下的牌上的数字时,高桥获胜,因此高桥有概率获胜 \frac49.
示例输入 2
2 9988# 1122#
示例输出 2
1.0
示例输入 3
6 1122# 2228#
示例输出 3
0.001932367149758454
仅当高桥的手牌为 11222 青木的手是 22281,有概率 \frac2{1035}.
示例输入 4
100000 3226# 3597#
示例输出 4
0.6296297942426154