Fișierul intrare/ieșire | biperm.in, biperm.out | Sursă | OJI 2013, Clasele 11-12 |
---|---|---|---|
Autor | Zoltan Szabo | Adăugată de | Claudiu • coco |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 20480 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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ă.