Ефект метелика#8182

Ефект метелика

1 секунда

256 мегабайтів

Легка

Задано кілька подій, які відбуваються послідовно. Кожна подія може завершитися позитивним або негативним результатом і впливає на ймовірності результатів наступних подій.

Події відбуваються в порядку, заданому у вхідних даних. Для кожної події $i$ задано ціле базове значення $b_{i}$ b_i. Щоб визначити результат події, кидається симетричний $m$ -гранний кубик з гранями, пронумерованими від $1$ до $m$ , і значення, що випало, додається до базового значення. Якщо отримана сума строго позитивна, результат вважається позитивним; в іншому випадку (в тому числі при нульовому результаті) результат вважається негативним.

Якщо подія $i$ завершилася позитивним результатом, базові значення всіх наступних подій змінюються згідно з набором модифікаторів: для кожного $j > i$ j > i нове значення стає рівним $b_{j} + p_{ij}$ b_j + p_{ij}, де $p_{ij}$ p_{ij} — модифікатор для події $j$ . Якщо ж результат негативний, використовуються інші модифікатори: нове значення дорівнює $b_{j} + q_{ij}$ b_j + q_{ij}, де $q_{ij}$ q_{ij} — відповідний модифікатор.

Дозволяється втрутитися не більш ніж у $k$ подій. При втручанні замість одного кидка кубика виконуються два, після чого можна вибрати будь-який з отриманих результатів. Для кожної події рішення про втручання приймається безпосередньо перед кидком, з урахуванням результатів усіх попередніх подій.

Потрібно максимізувати ймовірність того, що остання подія завершиться позитивним результатом.

Вхідні дані

Перший рядок містить три цілих числа $n, k$ та $m (1 \leq k \leq n \leq 20, 4 \leq m \leq 1000)$ m~(1 \le k \le n \le 20, 4 \le m \le 1000) — кількість подій, максимально допустиму кількість втручань і кількість граней кубика.

Далі йдуть $3 n$ рядків, що описують події:

Рядок $3 i - 2$ 3i - 2: одне ціле число $b_{i}$ b_i — базове значення події $i (∣ b_{i} ∣ \leq 2000)$ i~(|b_i| \le 2000).
Рядок $3 i - 1$ 3i - 1: $n - i$ n - i цілих чисел $p_{i, i + 1}, \dots, p_{i, n}$ p_{i,i+1}, \dots, p_{i,n} — модифікатори для наступних подій при позитивному результаті події $i$ $(∣ p_{ij} ∣ \leq 2000)$ (|p_{ij}| \le 2000).
Рядок $3 i$ : $n - i$ n - i цілих чисел $q_{i, i + 1}, \dots, q_{i, n}$ q_{i,i+1}, \dots, q_{i,n} — модифікатори для наступних подій при негативному результаті події $i$ $(∣ q_{ij} ∣ \leq 2000)$ (|q_{ij}| \le 2000).

Для останньої події модифікатори відсутні, тому відповідні два рядки порожні.

Вихідні дані

Виведіть одне число — максимальну ймовірність того, що остання подія завершиться позитивним результатом. Відповідь має бути виведена з точністю до $6$ знаків після десяткової крапки.

Приклади

Приклад 1

Приклад 2