Diferente pentru problema/worms intre reviziile #19 si #35

Diferente intre titluri:

worms
Worms

Diferente intre continut:

== include(page="template/taskheader" task_id="worms") ==
Spiro a descoperit o noua specie de rame. Aceste a observat ca fiecare individ are un anumit nivel care ii determina puterea sa de lupta: daca individul respectiv are o putere de baza $p$ si un nivel $n$ atunci puterea acestuia de lupta este p^n^. Initial, Spiro are un grup de $Nr$ rame cu nivelele cuprinse intre $0$ si $15$. Aceste rame se vor da in fisierul de intrare sub forma unui vector <tex>a</tex> cu $16$ elemente, unde <tex>a_i</tex>( $0 &le; i &le; 15$), reprezinta numarul de rame de nivel $i$ (se garanteaza ca <tex>a_{15}>=1</tex>).
Spiro a descoperit o noua specie de rame. Aceste a observat ca fiecare individ are un anumit nivel care ii determina puterea sa de lupta: daca individul respectiv are o putere de baza $p$ si un nivel $n$ atunci puterea acestuia de lupta este p^n^. Initial, Spiro are un grup de $Nr$ rame cu nivelele cuprinse intre $0$ si $7$. Aceste rame se vor da in fisierul de intrare sub forma unui vector <tex>a</tex> cu $8$ elemente, unde <tex>a_i</tex>( $0 &le; i &le; 7$), reprezinta numarul de rame de nivel $i$ (se garanteaza ca <tex>a_{7}>=1</tex>).
Spiro vrea sa isi distribuie colectia intr-o ferma de rame. Astfel, el are la dispozitie o retea de $N$ camere numerotate de la $1$ la $N$ care sunt legate intre ele prin $M$ tunele. Tunele nu se suprapun si nu pot traversa unul peste celalat intrucat ferma de rame este foarte subtire si nu ar avea loc efectiv sa se intample asta. Cu alte cuvinte daca exista $2$ tunele care se intersecteaza, cu siguranta in acel punct se afla o camera.
Apoi, in urmatoarele $Q$ zile, acesta efectueaza una din operatiile de mai jos:
* 1 n -> Spiro, prin abilitatile sale exceptionale de biolog, face rost de inca o rama de nivel $2 * n (0 &le; n &le; 7)$ si o adauga la grupul curent.
* 1 n -> Spiro, prin abilitatile sale exceptionale de biolog, face rost de inca o rama de nivel $2 * n (0 &le; n &le; 3)$ si o adauga la grupul curent.
* 2 x -> pentru ca lui Spiro ii place foarte mult grupul pe care il are in momentul respectiv, aceste face o copie la grup prin metode foarte dubioase de un extraordinar biolog, si il amplaseaza in camera cu indicele x. Cand un nou grup este amplasat intr-o camera, ramele care formeaza acest grup se vor imperechea cu orice rama deja existenta in acea camera. Astfel, dupa ce un grup este amplasat, in acea camera se afla ramele care erau deja acolo, ramele din grupul amplasat si alte $nr1 * nr2$ rame rezultate din imperecherea fiecarei rame care era deja in camera cu fiecare rama din grupul amplasat ( $nr1$ = numarul de rame care erau deja in camera si $nr2$ = numarul de rame din grupul amplasat). Cand o rama de nivel $n1$ se imperecheaza cu o rama de nivel $n2$, atunci rama rezultata va avea nivelul $n = n1 + n2$. Initial, toate camerele nu contin nicio rama.
Deoarece, din nou, Spiro este un extraordinar biolog, acesta poate crea orice tip de hrana $h$ astfel incat rama care mananca tipul respectiv de hrana va avea puterea de baza $h$ ( $h$ este un numar real). Puterea de lupta a ramelor dintr-o camera este suma puterilor de lupta a fiecarei rame din camera respectiva. Deoarece ramele sunt foarte batause, daca o camera $x$ are puterea de lupta mai mare ca o camera vecina cu ea $y$, atunci ramele din camera $x$ se vor duce peste ramele din camera $y$ si le vor omori. Lucru ce este imposbil, deoarece, pe langa un extraordinar biolog, Spiro mai e este si pacifist si ar vrea ca ferma sa sa ramana intreaga. Astfel, el trebuie sa aleaga pentru fiecare camera ce tip de hrana sa puna acolo astfel incat puterile de lupta ale oricaror doua camere vecine sa fie egale. Totusi, Spiro are un frate mai mic, Piro, care nu stie atat de multe lucruri despre rame si puteri si a.m.d., dar totusi stie sa diferentieze ramele intre ele si ar vrea, pentru ca ferma sa arate frumos, ca ramele din oricare doua camere vecine sa arate diferit. Deoarece aspectul ramelor este direct legat de hrana acestora, Spiro trebuie sa aleaga hrana pentru fiecare camera asfel incat doua camera vecine sa aiba hrana atribuita diferite.
h2. Date de intrare
Fişierul de intrare $worms.in$ contine pe prima linie $16$ numere reprezentand vectorul <tex>a</tex>. Pe urmatoare linie se afla doua numere $N$ si $M$. Pe urmatoarele $M$ linii se afla cate doua numere $x$ si $y$ reprezentand un tunel intre camerele $x$ si $y$. Pe urmatoarea linie se afla $Q$. Pe urmatoarele $Q$ linii se afla cate o operatie de forma celor de mai sus.
Fişierul de intrare $worms.in$ contine pe prima linie $8$ numere reprezentand vectorul <tex>a</tex>. Pe urmatoare linie se afla doua numere $N$ si $M$. Pe urmatoarele $M$ linii se afla cate doua numere $x$ si $y$ reprezentand un tunel intre camerele $x$ si $y$. Pe urmatoarea linie se afla $Q$. Pe urmatoarele $Q$ linii se afla cate o operatie de forma celor de mai sus.
h2. Date de ieşire
h2. Restricţii
* $1 &le; N &le; ...$
* $1 &le; M &le; ...$
* Numarul de rame de nivel $n$ din grup dupa efectuarea celor $Q$ operatii &le; $10$, unde $0 &le; n &le; 15$
* $1 &le; N &le; 10000$
* $1 &le; M &le; 30000$
* Numarul de rame de nivel $n$ din grup dupa efectuarea celor $Q$ operatii &le; $10$, unde $0 &le; n &le; 7$
* $6$ &le; numarul de copii amplasate in camera $i$ &le; $12$, unde $1 &le; i &le; N$
* Puterea de lupta din camera $i$ trebuie sa fie &le; $10$^16^, unde $1 &le; i &le; N$
* Doua numere $a$ si $b$ sunt egale daca $abs ( a - b ) < 10^-9^ $
* Puterea de lupta din camera $i$ **trebuie** sa fie in modul &le; $10$^9^, unde $1 &le; i &le; N$
* Doua numere $a$ si $b$ sunt egale daca $abs(a - b) < 10$^-9^
h2. Exemplu
table(example). |_. worms.in |_. worms.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|0 0 0 0 0 0 0 1
2 1
1 2
3
2 1
1 3
2 2
| 1.0000000000
0.8986537126
|
h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="worms") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.