← 返回题目列表

Codeforces · 1275/D

D. 存储2

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

为了在 VKontakte 上可靠而紧凑地存储图片,使用了冗余代码。所有图片被分成15个组,并且对于每组图片计算13个冗余码。如果某些图片因硬盘故障而丢失,则需要冗余代码才能恢复这些图片。

在计算冗余码之前,将一组中的15张图片写入3行5列的矩阵中。接下来,在所得矩阵的右侧添加两列 6 个冗余代码(每对代码根据同一行的图片计算),然后在底部添加另一行 7 个冗余代码(每对代码根据同一列的图片或冗余代码计算)。

我们将图片和冗余代码称为块。因此,从 15 张图片中,我们收到了 28 个块,以 4 x 7 矩阵的形式排列。在这个问题中,不会给出计算冗余码的公式,但给出了它们的性质:即使用一列中的任意3个块,可以明确地恢复同一列中丢失的第四个块,并且使用一行中的任意5个块,可以明确地恢复同一行中剩余的两个块(如果它们丢失)。当然,恢复操作可以以任意顺序对不同的行和列应用多次,并且在后续操作中,可以使用先前恢复的块。

假设您有 28 个块(15 张图片和 13 个冗余代码),并且您随机丢失了其中 $$$k$$$(在所有选项中可能性相同)。你的任务是计算 15 张图片中至少一张无法恢复的概率,以及丢失图片数量的预期。

输入

唯一的输入行包含整数 $$$k$$$ ($$$0 \le k \le 28$$$) — 丢失块的数量。

输出

打印两个数字:从剩余块中至少无法恢复一张图片的概率,以及从剩余块中无法恢复的图片数量的期望。

如果答案的绝对或相对误差不超过 $$$10^{-9}$$$,则答案将被视为正确。

示例

输入 #1

28

输出 #1

1.00000000000000000000 15.00000000000000000000

输入 #2

6

输出 #2

0.00055741360089186175 0.00179168657429526999

注意

在第一个示例中,所有 28 个块都丢失了,显然,100% 的概率所有 15 张图片都丢失了。

在第二个示例中,只有 376740 幅图像中有 210 幅无法恢复至少一张图片,因此概率为 $$$210/376740$$$。根据丢失块的位置,将无法恢复 1 到 6 张图片,预期值为 $$$15/8372$$$。

有两种可能的方式来丢失 6 个区块。

在第一种情况下,丢失了3张图片和3个冗余代码(用叉号标记)。首先,我们可以恢复第一行中的一个丢失块(使用同一行中的其他 5 个)并恢复第四行中的两个丢失块(使用同一行中的其他 5 个)。然后我们可以重建剩余的三个块(使用相应列中的其他 3 个块)。请注意,按列恢复时,我们还使用了第一步中恢复的块。因此,我们能够恢复所有块,并且没有丢失任何一张图片。

在第二种情况下,丢失了4张图片和2个冗余代码。第二行和第三行各有三个丢失的块,这意味着我们无法明确恢复其中的任何块。类似地,第三、第五和第七列各有两个丢失的块,这意味着我们无法明确恢复其中的任何块。剩下的行列中,所有的方块都完好无损,没有什么可以恢复的。因此,我们将无法恢复六个丢失块中的任何一个,但其中只有四个是图片。