== include(page="template/taskheader" task_id="generatoare") ==
Avem $n$ generatoare de numere notate {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~n~}$}. Generatorul {$G{~i~}$} generează aleator un număr natural {$a{~i~}$} cuprins între {$0$} şi {$m{~i~}-1$}, fiecare număr având aceeaşi probabilitate de a fi generat. Notăm cu **{$vxor$}** valoarea {$a{~1~}$} xor {$a{~2~}$} xor ... xor {$a{~n~}$}. Să se determine “valoarea aşteptată” pentru **{$vxor$}** ştiind că aceasta este egală cu suma !problema/generatoare?ecuatie.png!, unde cu {$Val$} am notat mulţimea valorilor ce pot fi obţinute pentru **{$vxor$}** iar cu {$p(v)$} am notat probabilitatea ca valoarea obţinută pentru **{$vxor$}** să fie {$v$}.
Avem $n$ generatoare de numere notate {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~n~}$}. Generatorul {$G{~i~}$} generează aleator un număr natural {$a{~i~}$} cuprins între {$0$} şi {$m{~i~}-1$}, fiecare număr având aceeaşi probabilitate de a fi generat. Notăm cu **{$vxor$}** valoarea {$a{~1~}$} xor {$a{~2~}$} xor ... xor {$a{~n~}$}. Să se determine “valoarea aşteptată” pentru **{$vxor$}** ştiind că aceasta este egală cu suma !problema/generatoare?ecuatie.png!, unde cu {$Val$} am notat mulţimea valorilor ce pot fi obţinute pentru **{$vxor$}** iar cu {$p(v)$} am notat probabilitatea ca valoarea obţinută pentru **{$vxor$}** să fie {$v$}.
Scrieţi un program care să determine “valoarea aşteptată” pentru **{$vxor$}**.
h2. Date de intrare
Fişierul de intrare $generatoare.in$ ...
Pe prima linie a fişierului de intrare $generatoare.in$ se află numărul natural $n$ reprezentând numărul de generatoare. Pe următoarele $n$ linii se află numerele {$m{~1~}$}, {$m{~2~}$}, ..., {$m{~n~}$}, câte unul pe o linie. Mai exact, pe linia {$i+1$} se află valoarea {$m{~i~}$}.
h2. Date de ieşire
În fişierul de ieşire $generatoare.out$ ...
Fişierul de ieşire $generatoare.out$ va conţine o singură linie pe care se află “valoarea aşteptată” pentru {$**vxor**$} cu exact $3$ zecimale cu rotunjire.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 50000$
* $2 ≤ m{~i~} ≤ 2^30^$
* Pentru două numere naturale $a$ şi {$b$}, definim $a xor b$ valoarea obţinută aplicând operatorul „sau exclusiv” pe reprezentările binare ale lui $a$ şi {$b$}.
h2. Exemplu
table(example). |_. generatoare.in |_. generatoare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
3
5
| 2.200
|
h3. Explicaţie
...
Avem două generatoare. Primul poate genera numerele $0$, $1$, $2$ iar al doilea numerele $0$, $1$, $2$, $3$, $4$. Deci perechea ({$a{~1~}$},{$a{~2~}$}) poate avea următoarele valori: $(0,0), (0,1), (0,2), (0,3), (0,4), (1,0), (1,1), (1,2), (1,3), (1,4), (2,0), (2,1), (2,2), (2,3), (2,4)$. Rezultă în ordine următoarele $15$ valori pentru $vxor$: $0, 1, 2, 3, 4, 1, 0, 3, 2, 5, 2, 3, 0, 1, 6$. Observăm că valorile distincte posibile pentru $vxor$ sunt $0, 1, 2, 3, 4, 5 şi 6$. Astfel, valorile $0, 1, 2 şi 3$ au probabilitatea de apariţie $3/15$ iar $4, 5 şi 6$ au probabilitatea de apariţie $1/15$. Deci, “valoarea aşteptată” pentru $vxor$ este $(0 + 1 + 2 + 3) * (3 / 15) + (4 + 5 + 6) * (1 / 15) = 2.200$.
== include(page="template/taskfooter" task_id="generatoare") ==
