Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-05-23 22:28:50.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sets.in, sets.outSursăONIS 2015, Runda Finala
AutorAdrian Budau, Mihai CalanceaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 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.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 1000
  • 1 ≤ A[i] ≤ 1000
  • 1 ≤ V <= 109
  • Valoarea afişată este considerată corectă dacă eroarea ei relativă este mai mică sau egală cu 10-6.

Exemplu

sets.insets.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?