Fişierul intrare/ieşire:echival1.in, echival1.outSursăLot Deva 2013 - Baraj 2 Seniori
AutorZoltan SzaboAdăugată dedarrenRares Buhai darren
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Echival1

Fie mulţimea M = {1, 2, 3, ... , n}. Vom defini o bipermutare de ordin n ca o matrice a cu două linii şi n coloane, în care fiecare număr k al mulţimii M apare în matrice pe două coloane distincte (figurile 1, 2, 3 şi 4 conţin câte o bipermutare, iar matricea din figura 0 nu este bipermutare). Într-o bipermutare putem efectua următoarele operaţii:

  • să schimbăm două elemente de pe o aceeaşi coloană (figura 1 => figura 2)
  • să schimbăm două coloane între ele (figura 1 => figura 3)
  • să schimbăm în bipermutare două valori distincte x şi y între ele (figura 1 => figura 4)

Două bipermutări sunt echivalente, dacă există o succesiune de operaţii prin care din prima bipermutare se poate ajunge la a doua bipermutare. În figurile de mai sus toate cele patru bipermutări sunt echivalente. Dacă două bipermutări sunt echivalente, atunci ele aparţin aceleiaşi clase de echivalenţă.

Cerinţă

Dându-se o bipermutare de ordin n verificaţi echivalenţa acesteia cu alte 10 bipermutări de ordin n.

Date de intrare

Fişierul de intrare echival1.in conţine pe prima linie numărul natural n, cu semnificaţia de mai sus. Următoarele 2 linii conţin câte n numere separate prin spaţiu şi descriu bipermutarea ce urmează a fi verificată, următoarele 20 de linii descriu analog cele 10 bipermutări ale setului, câte una pe două linii.

Date de ieşire

Fişierul de ieşire echival1.out va conţine pe 10 linii consecutive, în ordinea bipermutărilor citite din fişierul de intrare, câte un număr natural astfel: 1, dacă bipermutarea curentă este echivalentă cu prima bipermutare citită şi 0, în caz contrar.

Restricţii

  • 2 < n ≤ 100000

Exemplu

echival1.inechival1.out
5
5 3 4 1 2
2 4 1 3 5
5 2 4 4 1
3 1 5 3 2
1 1 2 3 4
2 4 5 5 3
1 1 5 3 4
4 3 2 2 5
2 1 3 4 4
1 5 2 3 5
3 2 4 1 1
5 3 2 4 5
3 4 5 5 1
4 2 3 1 2
1 3 2 3 4
4 1 5 5 2
5 2 5 1 1
3 4 2 4 3
4 4 5 2 1
1 2 3 3 5
3 5 3 2 2
1 1 5 4 4
1
0
0
0
0
0
0
0
0
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content