306942: CF1275D. Storage2

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Storage2

题目描述

Для надежного, но компактного хранения картинок во ВКонтакте используются избыточные коды. Все картинки разбиваются на группы по 15, и для каждой группы картинок вычисляются 13 избыточных кодов. Избыточные коды необходимы, чтобы суметь восстановить некоторые картинки, если они будут утеряны вследствие поломки жесткого диска. Перед вычислением избыточных кодов 15 картинок из одной группы записываются в матрицу из 3 строк и 5 столбцов. Далее к получившейся матрице справа добавляются два столбца с 6 избыточными кодами (каждая пара кодов вычисляется на основе картинок в той же строке), а затем снизу добавляется еще одна строка из 7 избыточных кодов (каждый из них считается на основе картинок или избыточных кодов в том же столбце). ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1275D/eadc184fb5f5a4736bb0851971b7a16384691f32.png)Будем называть картинки и избыточные коды блоками. Таким образом, из 15 картинок мы получили 28 блоков, расставленных в виде матрицы 4 на 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

Input

暂时还没有翻译

加入题单

上一题 下一题 算法标签: