Fişierul intrare/ieşire:minmaxstore.in, minmaxstore.outSursăONIS 2016 Runda Online
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Min Max Store

Popel si Popita au un vector V cu N elemente distincte. Popel vrea sa determine elementul minim si Popita elementul maxim din acest vector. Acestia primesc o serie de operatii de tipul STORE care pun in pozitia A minimul si in B maximul dintre cele 2 valori. Mai exact, V[A] = min(V[A], V[B]) si V[B] = max(V[A], V[B]). La sfarsit, cei 2 dau 2 pozitii reprezentand pozitia la care se afla elementul minim, respectiv elementul maxim. Cand Comisarul a venit sa verifice daca Popel si Popita isi fac treaba cum trebuie, acestia observa ca au pierdut vectorul initial si nu au cum sa ii arate Comisarului daca au dat pozitiile de mimim si maxim corecte. Singura lor scapare este daca cele 2 pozitii sunt valide pentru orice permutare de lungime V. Mai exact, pentru orice permutare P de lungime N, daca aplicam operatiile de STORE date, elementul minim si maxim se pozitioneaza pe cele 2 pozitii date de personajele noastre.

Date de intrare

Fişierul de intrare minmaxstore.in va contine pe prima linie un numar natural T, numarul de teste. Pentru fiecare test, prima linie va contine 2 numere naturale N si M, lungimea vectorului si numarul de operatii STORE. Urmatoarele M linii contin cate 2 numere naturale A si B reprezentand cate o operatie de tipul STORE. Ultima linie contine alte 2 numere PMIN si PMAX, pozitia minimului si a maximului.

Date de ieşire

Fişierul de ieşire minmaxstore.out va contine T linii, pe linia i aflandu-se raspunsul pentru testul i:

  • Daca doar Popel a dat un raspuns valid, raspunsul este "Popel"
  • Daca doar Popita a nimerit, raspunsul este "Popita"
  • Daca amandoi au dat un raspuns corect, afisati "Popeala"
  • Daca niciunul nu a nimerit, afisati "Comisarul"

Restricţii

  • 1 ≤ Suma M-urilor dintr-un fisier va fi ≤ 1.000.000
  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 200.000

Exemplu

minmaxstore.inminmaxstore.out
4
4 5
1 2
1 3
1 4
2 4
3 4
1 4
3 2
1 2
1 3
1 3
3 3
1 2
1 3
2 3
2 3
2 1
2 1
1 2
Popeala
Popel
Popita
Comisarul
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?