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$.
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 $[0, V]$ sunt norocoase în medie relativ la submulţimea $B$?
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$?
h2. Date de intrare
Fişierul de intrare $sets.in$ ...
Fişierul de intrare $sets.in$ va conţine pe prima sa linie numărul de teste $T$. Urmează $T$ teste, fiecare având următoarea structură: prima linie conţine numerele $N$ şi $V$, având semnificaţia din enunţ. A doua linie conţine $N$ numere întregi, reprezentând mulţimea $A$.
h2. Date de ieşire
În fişierul de ieşire $sets.out$ ...
În fişierul de ieşire $sets.out$ se vor afla $T$ linii, fiecare conţinând o valoare reală, răspunsul pentru fiecare test în parte.
h2. Restricţii
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 1000$
* $1 ≤ A[i] ≤ 1000$
* $1 ≤ V <= 10^9^ ≤ 1000$
* $1 ≤ V ≤ 10^9^$
* Valoarea afişată este considerată corectă dacă eroarea ei relativă este mai mică sau egală cu 10^-6^.
h2. Exemplu
h3. 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$
== include(page="template/taskfooter" task_id="sets") ==
