| Fişierul intrare/ieşire: | dezastru.in, dezastru.out | Sursă | preONI 2007, Runda 4 |
| Autor | Adrian Diaconu, Tiberiu-Lucian Florea | Adăugată de |  Tiberiu-Lucian Florea •greco |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Dezastru
Ziua Dezastrului a sosit. Conform lui L. Ron Hubbard, din cauza numarului mic de persoane inscrise la Scientology, extraterestrii vor supune Pamantul la N atacuri consecutive. Pe langa faptul ca au construit un scut care va apara Pamantul dupa primele K asalturi, oamenii au calculat probabilitatile p1, p2, .. pN de a supravietui fiecaruia dintre atacurile planificate. Ramane o singura problema: nu se stie in ce ordine vor avea loc aceste atacuri, fiecare dintre cele N! variante fiind la fel de probabila ca si celelalte.
Stii ca probabilitatea supravietuirii la x atacuri este egala cu produsul probabilitatilor individuale. Ti se cere sa calculezi probabilitatea ca Pamantul sa reziste primelor K atacuri, salvandu-se astfel de Dezastru.
Date de intrare
Pe prima linie a fisierului dezastru.in se gasesc numerele naturale si pozitive N si K. Pe urmatoarea linie se afla N numere reale, reprezentand probabilitatea ca Pamantul sa reziste fiecaruia dintre cele N atacuri asteptate.
Date de iesire
Pe prima linie a fisierului dezastru.out se va scrie un singur numar real cu 6 zecimale: probabilitatea supravietuirii primelor K atacuri, dupa care Pamantul va porni scutul cosmic. Raspunsul va fi verificat cu o precizie de 0.000001.
Restrictii
- 1 ≤ N ≤ 25
- K ≤ N
Exemplu
| dezastru.in | dezastru.out |
|---|---|
| 3 2 0.3 0.5 0.8 | 0.263333 |
Explicatie
| Permutare | Probabilitate sa supravietuiasca primelor 2 atacuri |
|---|---|
| 1 2 3 | 0.3 * 0.5 = 0.15 |
| 1 3 2 | 0.3 * 0.8 = 0.24 |
| 2 1 3 | 0.5 * 0.3 = 0.15 |
| 2 3 1 | 0.5 * 0.8 = 0.40 |
| 3 1 2 | 0.8 * 0.3 = 0.24 |
| 3 2 1 | 0.8 * 0.5 = 0.40 |
Sunt in total 6 permutari deci fiecare va aparea cu probabilitatea 1/6.
Solutie: 0.15/6 + 0.24/6 + 0.15/6 + 0.40/6 + 0.24/6 + 0.40/6 = 0.263333
