Diferente pentru problema/tequila intre reviziile #125 si #144

Nu exista diferente intre titluri.

Diferente intre continut:

Intors acasa de la ONI, Antonio se plimba prin Gradina Publica din Barlad impreuna cu cel mai bun prieten al sau, Zetul.
Antonio ii spune lui Zetul urmatoarea problema, care se va da la JBOI 2016 (informatie sigura, aflata de Antonio):
Antonio si-a imaginat o firma cu $N$ angajati, numerotati de la $1$ la $N$. Fiecare angajat al firmei are cate un sef direct (in afara de seful suprem), iar fiecare angajat il are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, $val{~X~}$.
Antonio si-a imaginat o firma cu $N$ angajati, numerotati de la $1$ la $N$. Fiecare angajat al firmei are cate un sef direct (in afara de seful suprem), iar fiecare angajat il are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, <tex> val_X </tex>.
Exista $2$ tipuri de operatii:
Exista <tex> 2 </tex> tipuri de operatii:
* Update: Noua valoarea asociata angajatului $X$ va fi $Y$;
* Update: Noua valoarea asociata angajatului <tex> X </tex> va fi <tex> Y </tex>;
* Query: **Cat timp** seful suprem nu este concediat, Zetul alege **la intamplare** un angajat $X$ si va fi nevoit sa bea $val{~X~}$ shot-uri de tequila, iar apoi il va concedia atat pe $X$ cat si pe toti angajatii care il au ca sef indirect pe $X$. Antonio este curios cate shot-uri de tequila va bea Zetul **in medie** (eng. "expected value").
* Query: **Cat timp** seful suprem nu este concediat, Zetul alege **la intamplare** un angajat <tex> X </tex> si va fi nevoit sa bea <tex> val_X </tex> shot-uri de tequila, iar apoi il va concedia atat pe <tex> X </tex> cat si pe toti angajatii care il au ca sef indirect pe <tex> X </tex>. Antonio este curios cate shot-uri de tequila va bea Zetul **in medie** (eng. "expected value").
h2. Cerinta
Fisierul de intrare $tequila.in$ va contine pe prima linie doua numere naturale <tex> N </tex> si <tex> M </tex>, reprezantand numarul de angajati ai firmei si, respectiv, numarul de update-uri;
Urmatoarea linie va contine <tex> N </tex> numere naturale - pentru fiecare angajat <tex> X </tex> (<tex> 1 \leq X \leq N </tex>) valoarea asociata initial, <tex> val_X </tex>;
Urmatoarele <tex> N </tex> linii vor descrie firma - pentru fiecare angajat <tex> X </tex> (<tex> 1 \leq X \leq N </tex>), seful direct al acestuia;
Urmatoarele <tex> M </tex> linii vor descrie operatiile de update sub forma: <tex> X \hspace Y </tex> (noua valoare asociata lui <tex> X </tex> este <tex> Y </tex>, echivalent cu <tex> val_X = Y </tex>);
Urmatoarele <tex> M </tex> linii vor descrie operatiile de update sub forma: <tex> X \: Y </tex> (noua valoare asociata lui <tex> X </tex> este <tex> Y </tex>, echivalent cu <tex> val_X = Y </tex>).
h2. Date de ieşire
h2. Restricţii si precizari
* $1 &le; val{~X~} &le; 100.000$ ({$1 &le; X &le; N$})
* <tex> 1 \leq val_X \leq 100 \: 000 \: (1 \leq X \leq N) </tex>
* Seful suprem va avea seful direct codificat cu $-1$.
* Seful suprem va avea seful direct codificat cu <tex> -1 </tex>. (nu este neaparat angajatul codificat cu <tex> 1 </tex>)
* Fie $Y$ seful direct al angajatului $X$. Spunem ca un angajat este **sef indirect** al lui $X$ daca acesta este fie $Y$, fie un sef indirect al lui $Y$.
* Fie <tex> Y </tex> seful direct al angajatului <tex> X </tex>. Spunem ca un angajat este **sef indirect** al lui <tex> X </tex> daca acesta este fie <tex> Y </tex>, fie un sef indirect al lui <tex> Y </tex>.
* Dupa o operatie de query, Zetul va angaja la loc toti membrii firmei.
* Rezultatul afisat se va considera corect daca si numai daca fie eroarea absoluta, fie cea relativa este pana in <tex> 10^-^5 </tex>. Mai exact, fie <tex> \(\mid rezultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid \leq 10^-^5\) </tex>, fie <tex> \(\frac{\mid rezultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid}{rezultat_c_o_m_i_s_i_e} \leq 10^-^5\) </tex>.
* Rezultatul afisat se va considera corect daca si numai daca fie eroarea absoluta, fie cea relativa este pana in <tex> 10^-^5 </tex>. Mai exact, fie <tex> \(\mid rezultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid \leq 10^-^5\) </tex>, fie <tex> \(\frac{\mid relzultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid}{rezultat_c_o_m_i_s_i_e} \leq 10^-^5\) </tex>.
* Antonio foloseste mult expresia "pe mangleala" si cuvantul "gen".
* **Subtask 1 (30 puncte)**: <tex> 1 \leq N \leq 20 </tex>, <tex> M = 0 </tex>
* **Subtask 2 (20 puncte)**: <tex> 1 \leq N \cdot M \leq 4.000.000$ </tex>, <tex> 1 \leq M \leq 4.000 </tex> si nu vor exista $2$ angajati cu acelasi sef direct
* **Subtask 3 (50 puncte)**: <tex> 1 \leq N \leq 100.000 </tex>, <tex> 1 \leq M \leq 100.000 </tex>
* **Subtask 1 (30 puncte)**: <tex> 1 \leq N \leq 20 </tex>, <tex> M = 0 </tex> (Feedback testul <tex> 2 </tex>)
* **Subtask 2 (20 puncte)**: <tex> 1 \leq N \cdot M \leq 4 \: 000 \: 000$ </tex>, <tex> 1 \leq M \leq 4 \: 000 </tex> si nu vor exista <tex> 2 </tex> angajati cu acelasi sef direct (Feedback testul <tex> 9 </tex>)
* **Subtask 3 (50 puncte)**: <tex> 1 \leq N \leq 100 \: 000 </tex>, <tex> 1 \leq M \leq 100 \: 000 </tex> (Feedback testul <tex> 15 </tex>)
h2. Exemplu
  1
  1 2
| 2.00000
  3.00000
  3.00000 |
| 3 0
  1 1 1
  2
 -1
  1
| 1.83333
|
 
 
 
h3. Explicaţie
Exista $5$ posibilitati de a concedia angajatii (considerand si ordinea concedierilor):
Pentru testul <tex> 1 </tex>, exista <tex> 5 </tex> posibilitati de a concedia angajatii **(considerand si ordinea concedierilor)**:
# Angajatul **$1$** cu probabilitatea <tex> \(\frac{1}{3}\) </tex> - in acest caz Zetul va bea <tex> val_1 </tex> shot-uri;
# Angajatii **$2$**, **$1$** cu probabilitatea <tex> \(\frac{1}{3} \cdot \frac{1}{2}\) </tex> - in acest caz Zetul va bea <tex> val_2 + val_1 </tex> shot-uri;
Asadar:
# Pentru valorile asociate initial Zetul va bea in medie <tex> \(\frac{1}{3} + \frac{2}{6} + \frac{2}{6} + \frac{3}{6} + \frac{3}{6} = 2\) </tex> shot-uri de tequila;
# Dupa primul update Zetul va bea in medie <tex> \[\frac{2}{3} + \frac{3}{6} + \frac{3}{6} + \frac{4}{6} + \frac{4}{6} = 3\] </tex> shot-uri de tequila;
# Pentru valorile asociate initial, Zetul va bea in medie <tex> \(\frac{1}{3} + \frac{2}{6} + \frac{2}{6} + \frac{3}{6} + \frac{3}{6} = 2\) </tex> shot-uri de tequila;
# Dupa primul update, Zetul va bea in medie <tex> \[\frac{2}{3} + \frac{3}{6} + \frac{3}{6} + \frac{4}{6} + \frac{4}{6} = 3\] </tex> shot-uri de tequila;
== include(page="template/taskfooter" task_id="tequila") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.