Fișierul intrare/ieșire biperm.in, biperm.out Sursă OJI 2013, Clasele 11-12
Autor Zoltan Szabo Adăugată de avatar coco Claudiu coco
Timp de execuție pe test 0.2 sec Limită de memorie 20480 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Biperm (clasele 11-12)

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.

Cerinta

Cunoscând o bipermutare, determinați:
• numărul bipermutărilor perfecte distincte ce se pot obține prin mutări;
• numărul minim de mutări prin care se poate obține o bipermutare perfectă;
• o bipermutare perfectă obținută din bipermutarea inițială.

Date de intrare

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.

Date de ieșire

Fișierul de ieșire biperm.out va conține:
• pe prima linie două numere naturale separate printr-un spațiu, reprezentând numărul bipermutărilor perfecte distincte ce se pot obține din bipermutarea dată, respectiv numărul minim de mutări prin care se poate obține o bipermutare perfectă;
• pe următoarele două linii se vor tipări câte n numere separate prin spațiu, reprezentând o bipermutare perfectă obținută din bipermutarea dată.

Restricții

• 2 < n < 10 000;
• Pot exista mai multe soluții, se va admite orice soluție corectă;
• se garantează că numărul bipermutărilor perfecte distincte nu depășește 2 000 000 000 pentru niciun test.
• acordarea punctajului la un răspuns corect este condiționată de existența răspunsurilor anterioare, indiferent de corectitudinea lor;

Exemplu

biperm.in biperm.out
5
1 5 5 3 4
3 2 2 4 1
4 1
1 2 5 3 4
3 5 2 4 1

Explicație

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 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 1 2 5 3 4
Pentru a treia cerință oricare dintre cele 4 soluții este acceptată.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii