generatoare

Generatoare

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

 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") ==

7325