Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | tequila.in, tequila.out | Sursă | Junior Challenge 2016 |
Autor | Alexandru Niculae, Costin Oncescu | Adăugată de | JuniorChallenge2016 •JuniorChallenge2015 |
Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tequila
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, valX.
Exista 2 tipuri de operatii:
- Update: Noua valoarea asociata angajatului X va fi Y;
- Query: Cat timp seful suprem nu este concediat, Zetul alege la intamplare un angajat X si va fi nevoit sa bea valX 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").
Cerinta
Pentru valorile asociate initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati raspunsul la operatia de query.
Date de intrare
Fisierul de intrare tequila.in va contine pe prima linie doua numere naturale si , reprezantand numarul de angajati ai firmei si, respectiv, numarul de update-uri;
Urmatoarea linie va contine numere naturale - pentru fiecare angajat () valoarea asociata initial, ;
Urmatoarele linii vor descrie firma - pentru fiecare angajat (), seful direct al acestuia;
Urmatoarele linii vor descrie operatiile de update sub forma: (noua valoare asociata lui este , echivalent cu ).
Date de ieşire
Fişierul de ieşire tequila.out va contine linii, reprezentand raspunsul pentru fiecare query in parte.
Restricţii si precizari
- Seful suprem va avea seful direct codificat cu .
- Fie seful direct al angajatului . Spunem ca un angajat este sef indirect al lui daca acesta este fie , fie un sef indirect al lui .
- 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 . Mai exact, fie , fie .
- Antonio foloseste mult expresia "pe mangleala" si cuvantul "gen".
- Subtask 1 (30 puncte): ,
- Subtask 2 (20 puncte): , si nu vor exista 2 angajati cu acelasi sef direct
- Subtask 3 (50 puncte): ,
Exemplu
tequila.in | tequila.out |
---|---|
3 1 1 1 1 -1 1 1 1 2 | 2.00000 3.00000 |
Explicaţie
Exista 5 posibilitati de a concedia angajatii (considerand si ordinea concedierilor):
- Angajatul 1 cu probabilitatea - in acest caz Zetul va bea shot-uri;
- Angajatii 2, 1 cu probabilitatea - in acest caz Zetul va bea shot-uri;
- Angajatii 3, 1 cu probabilitatea - in acest caz Zetul va bea shot-uri;
- Angajatii 2, 3, 1 cu probabilitatea - in acest caz Zetul va bea shot-uri;
- Angajatii 3, 2, 1 cu probabilitatea - in acest caz Zetul va bea shot-uri;
Asadar:
- Pentru valorile asociate initial Zetul va bea in medie shot-uri de tequila;
- Dupa primul update Zetul va bea in medie shot-uri de tequila;