Kəpənək effekti#8182

Kəpənək effekti

1 saniyə

256 meqabayt

Asan

Ardıcıl baş verən bir neçə hadisə verilmişdir. Hər hadisə müsbət və ya mənfi nəticə ilə başa çata bilər və sonrakı hadisələrin nəticə ehtimallarına təsir edir.

Hadisələr giriş məlumatlarında verilmiş sıra ilə baş verir. Hər $i$ hadisəsi üçün tam ədəd olan $b_{i}$ b_i baza dəyəri verilmişdir. Hadisənin nəticəsini müəyyən etmək üçün üzləri $1$ -dən $m$ -ə qədər nömrələnmiş simmetrik $m$ -üzlü zər atılır və çıxan dəyər baza dəyərinə əlavə edilir. Əgər alınan cəm ciddi müsbətdirsə, nəticə müsbət sayılır; əks halda (sıfır nəticə daxil olmaqla) nəticə mənfi sayılır.

Əgər $i$ hadisəsi müsbət nəticə ilə başa çatıbsa, bütün sonrakı hadisələrin baza dəyərləri modifikatorlar dəstinə uyğun olaraq dəyişdirilir: hər $j > i$ j > i üçün yeni dəyər $b_{j} + p_{ij}$ b_j + p_{ij} olur, burada $p_{ij}$ p_{ij} — $j$ hadisəsi üçün modifikatordur. Əgər nəticə mənfidirsə, digər modifikatorlar istifadə edilir: yeni dəyər $b_{j} + q_{ij}$ b_j + q_{ij} olur, burada $q_{ij}$ q_{ij} — müvafiq modifikatordur.

Ən çox $k$ hadisəyə müdaxilə etməyə icazə verilir. Müdaxilə zamanı bir zər atmaq əvəzinə iki zər atılır, bundan sonra alınan nəticələrdən istənilənini seçmək olar. Hər hadisə üçün müdaxilə qərarı birbaşa atışdan əvvəl, bütün əvvəlki hadisələrin nəticələri nəzərə alınaraq qəbul edilir.

Son hadisənin müsbət nəticə ilə başa çatma ehtimalını maksimumlaşdırmaq tələb olunur.

Giriş

Birinci sətirdə üç tam ədəd $n, k$ və $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) verilmişdir — hadisələrin sayı, icazə verilən maksimal müdaxilə sayı və zərin üzlərinin sayı.

Sonra hadisələri təsvir edən $3 n$ sətir gəlir:

$3 i - 2$ 3i - 2-ci sətir: bir tam ədəd $b_{i}$ b_i — $i$ hadisəsinin baza dəyəri $(∣ b_{i} ∣ \leq 2000)$ (|b_i| \le 2000).
$3 i - 1$ 3i - 1-ci sətir: $n - i$ n - i tam ədəd $p_{i, i + 1}, \dots, p_{i, n}$ p_{i,i+1}, \dots, p_{i,n} — $i$ hadisəsinin müsbət nəticəsi zamanı sonrakı hadisələr üçün modifikatorlar $(∣ p_{ij} ∣ \leq 2000)$ (|p_{ij}| \le 2000).
$3 i$ -ci sətir: $n - i$ n - i tam ədəd $q_{i, i + 1}, \dots, q_{i, n}$ q_{i,i+1}, \dots, q_{i,n} — $i$ hadisəsinin mənfi nəticəsi zamanı sonrakı hadisələr üçün modifikatorlar $(∣ q_{ij} ∣ \leq 2000)$ (|q_{ij}| \le 2000).

Son hadisə üçün modifikatorlar mövcud deyil, buna görə müvafiq iki sətir boşdur.

Çıxış

Bir ədəd çap edin — son hadisənin müsbət nəticə ilə başa çatma maksimal ehtimalı. Cavab onluq nöqtədən sonra $6$ rəqəm dəqiqliyilə çap edilməlidir.

Nümunələr

Nümunə 1

Nümunə 2