← 返回题目列表

AtCoder · abc193_d

D. 扑克

中文机器翻译题面 查看原题

分数: 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