Monede

Se consideră un șir de $N$ monede numerotate de la $0$ la $N - 1$. La o aruncare, moneda $i$ are probabilitatea $p[i]$ să cadă pajură, și $1 - p[i]$ să cadă cap.

Cerință

Pentru $Q$ intervale $[a, b]$ se cere să se afle probabilitatea ca, dacă s-ar arunca cu monedele $a, a + 1, \dots, b$, un număr impar de monede să pice pajură.

Interacțiune

Concurentul va include fișierul monede.h, realizând acest lucru prin directiva de preprocesor #include "monede.h". În acest header este implementată o structură de date Raport. Aceasta se poate utiliza în felul următor.

Raport r; 					// r se initializeaza cu valoarea 0 / 1 = 0
Raport p(1, 2); 			// p reprezinta raportul 1 / 2
Raport q = Raport(2, 3);	// q reprezinta raportul 2 / 3
bool b = (p == q); 			// b este fals, caci 1 / 2 != 2 / 3
Raport r = p + q; 			// r reprezinta 1 / 2 + 2 / 3 = 7 / 6.
Raport r = p - q; 			// r reprezinta 1 / 2 - 2 / 3 = - 1 / 6.
Raport r = p * q; 			// r reprezinta 1 / 2 * 2 / 3 = 1 / 3.
Raport r = p / q; 			// r reprezinta 1 / 2 : 2 / 3 = 3 / 4.
							// Se poate calcula si p * q, p / q, p - q
r -= p; 					// r devine 7 / 6 – 1 / 2 = 2 / 3.
							// Se putea efectua si r += p, r *= p, r /= p.

Concurentul va implementa două funcții. Prima este funcția init, având semnătura:

void init(int N, const Raport p[]);

Comisia va apela această funcție exact o dată, la începutul rulării programului, Funcția va primi prin parametrul $N$ (număr natural) numărul de monede și prin parametrul $p$ șirul de probabilități, indexat de la $0$.

A doua funcție este solve, cu semnătura:

Raport solve(int a, int b);

Comisia va apela această funcție de $Q$ ori. Funcția primește prin intermediul parametrilor $a$ și $b$ ($0 ≤ a ≤ b < N$) două poziții. Funcția va trebui să returneze răspunsul pentru intervalul $[a, b]$.

Concurentul nu implementează funcția main, ci funcțiile indicate în enunț, și oricare funcții auxiliare de care are nevoie!

Restricții și precizări

• $1 ≤ N ≤ 1 \ 000 \ 000$
• $1 ≤ Q ≤ 1 \ 000 \ 000$
• Valorile $a$ și $b$ trimise prin parametrii funcției solve respectă condiția $0 ≤ a ≤ b < N$.
• Pentru $23$ puncte, $N ≤ 15, Q ≤ 100$.
• Pentru alte $10$ puncte, $N ≤ 1 \ 000, Q ≤ 1 \ 000$.
• Pentru alte $37$ de puncte, $N, Q ≤ 200 \ 000$.
• Pentru alte $15$ de puncte, $p[i] \neq \frac{1}{2}$.

Exemplu

Intrare

N = 3
p = [1/4, 1/3, 1/2]

Ieșire

Solve(0, 0) = 1 / 4;
Solve(1, 1) = 1 / 3;
Solve(0, 1) = 5 / 12
Solve(0, 2) = Solve(1, 2) = Solve(2, 2) = 1 / 2