Fişierul intrare/ieşire:worms.in, worms.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 pn. 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 a cu 8 elemente, unde a_i( 0 ≤ i ≤ 7), reprezinta numarul de rame de nivel i (se garanteaza ca a_{7}>=1).
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 ≤ n ≤ 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.

Ajutati-l pe Spiro si spuneti-i ce hrana sa puna in fiecare camera astfel incat puterea de lupta a oricaror doua camere vecine sa fie aceeasi si hrana atribuita acestora sa fie diferita.

Date de intrare

Fişierul de intrare worms.in contine pe prima linie 8 numere reprezentand vectorul a. 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.

Date de ieşire

În fişierul de ieşire worms.out trebuie sa se afle N numere reale pe care o linie separata, al i-lea numar reprezentand tipul de hrana pus in camera i.

Restricţii

  • 1 ≤ N ≤ 10000
  • 1 ≤ M ≤ 30000
  • Numarul de rame de nivel n din grup dupa efectuarea celor Q operatii ≤ 10, unde 0 ≤ n ≤ 7
  • 6 ≤ numarul de copii amplasate in camera i12, unde 1 ≤ i ≤ N
  • Puterea de lupta din camera i trebuie sa fie in modul ≤ 109, unde 1 ≤ i ≤ N
  • Doua numere a si b sunt egale daca abs(a - b) < 10-9

Exemplu

worms.inworms.out
0 0 0 0 0 0 0 1
2 1
1 2
3
2 1
1 3
2 2
1.0000000000
0.8986537126
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?