biperm
Pentru un număr natural nenul n
, să considerăm toate numerele naturale nenule mai mici sau egale cu n
, luând fiecare număr de câte două ori: 1, 1, 2, 2, 3, 3, ... , n, n
. Aceste numere le amestecăm aleator, şi le aranjăm pe două linii a câte n
elemente. Structura astfel obţinută o vom numi o bipermutare. În figurile 1, 2
şi 3
avem câte un exemplu de bipermutare pentru n=5
.
O bipermutare este perfectă, dacă ambele linii ale structurii reprezintă câte o permutare (vezi figurile 2
şi 3
).
Prin mutare pe poziţia p
, înţelegem interschimbarea elementelor de pe aceeaşi coloană p
. În exemplele de mai jos, bipermutarea perfectă din figura 2
s-a obţinut din bipermutarea din figura 1
, aplicând o mutare pe poziţa 2
. Bipermutarea perfectă din figura 3
s-a obţinut din bipermutarea din figura 1
, aplicând mutări pe poziţiile 1, 2, 4
şi 5
.
Cunoscând o bipermutare, determinaţi:
Fişierul de intrare biperm.in
conţine pe prima linie valoarea lui n
. Următoarele două linii conţin, fiecare, câte n
elemente separate prin câte un spaţiu, formând o bipermutare.
Fişierul de ieşire biperm.out
va conţine:
2 < n ≤ 10 000
;30%
din punctaj;10%
din punctaj;60%
din punctaj. Pot exista mai multe soluţii, se va admite orice soluţie corectă;2 000 000 000
pentru niciun test.40%
din teste n ≤ 20
40%
din teste 20 < n ≤ 400
20%
din teste 400 < n ≤ 10 000
biperm.in
5
1 5 5 3 4
3 2 2 4 1
biperm.out
4 1
1 2 5 3 4
3 5 2 4 1
Sunt 4
permutări perfecte. Numărul minim de mutări este 1
şi există două soluţii cu număr minim de mutări:
1 2 5 3 4 1 5 2 3 4
3 5 2 4 1 şi 3 2 5 4 1
Celelalte două soluţii, ce nu se obţin din număr minim de mutări sunt:
3 2 5 4 1 3 5 2 4 1
1 5 2 3 4 şi 1 2 5 3 4
Pentru a treia cerinţă oricare dintre cele 4
soluţii este acceptată.
ID: 35
Upload: liviu
Input: biperm.in/biperm.out
Memory limit: 128MB/64MB
Time limit: 0.1s
Author: Zoltan Szabo
Source: OJI 2013 XI-XII: Problema 1