== 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$}**.
* $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$}.
* $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 |
| 2
3
| 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") ==
