Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sets.in, sets.out | Sursă | ONIS 2015, Runda Finala |
| Autor | Adrian Budau, Mihai Calancea | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sets
Fie M o mulţime de numere întregi şi X un număr întreg. Un algoritm în general incorect pentru a determina o submulţime a lui M care are suma X este următorul:
1. Dacă X este 0, algoritmul a avut succes.
2. Altfel găsim cel mai mare element Y din M cu proprietatea că Y este mai mic sau egal cu X. Dacă acest număr nu există algoritmul, eşuează (X fiind nenul). Dacă acest număr există, îl aducem pe X la valoarea X - Y şi reluăm pasul 1.
Numim numărul X norocos relativ la mulţimea M dacă algoritmul de mai sus se încheie cu succes pentru X şi M.
Dându-se o mulţime A de N elemente şi un număr V şi alegând aleator cu probabilitate uniformă o submulţime a sa, fie ea B, câte numere din intervalul [1, V] sunt norocoase în medie relativ la submulţimea B?
Date de intrare
Fişierul de intrare sets.in ...
Date de ieşire
În fişierul de ieşire sets.out ...
Restricţii
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 1000
- 1 ≤ A[i] ≤ 1000
- 1 ≤ V <= 109 ≤ 1000
Exemplu
| sets.in | sets.out |
|---|---|
| 2 2 3 1 2 5 16 1 2 3 4 6 | 1.7500000000 11.5000000000 |
Explicaţie
În primul exemplu avem următoarele patru submulţimi care pot fi selectate, fiecare având probabilitate 25%:
1. {}
În acest caz algoritmul eşuează pentru orice număr întreg.
2. {1}
În acest caz 1, 2, 3 sunt numere norocoase.
3. {2}
În acest caz 2 este număr norocos.
4. {1, 2}
În acest caz 1, 2, 3 sunt toate numere norocoase.
Astfel răspunsul este 0.25 * (0 + 3 + 1 + 3) = 1.75
