Fişierul intrare/ieşire:biperm.in, biperm.outSursăOJI 2013, clasele 11-12
AutorZoltan SzaboAdăugată devisanrVisan Radu visanr
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Biperm

Pentru un numar natural nenul n, sa consideram toate numerele naturale nenule mai mici sau egale cu n, luand fiecare numar de cate doua ori: 1, 1, 2, 2, 3, 3, ... , n, n. Aceste numere le amestecam aleator, si le aranjam pe doua linii a cate n elemente. Structura astfel obtinuta o vom numi o bipermutare. In figurile 1, 2 si 3 avem cate un exemplu de bipermutare pentru n=5.
O bipermutare este perfecta, daca ambele linii ale structurii reprezinta cate o permutare (vezi figurile 2 si 3).
Prin mutare pe pozitia p, intelegem interschimbarea elementelor de pe aceeasi coloana p. In exemplele de mai jos, bipermutarea perfecta din figura 2 s-a obtinut din bipermutarea din figura 1, aplicand o mutare pe pozitia 2. Bipermutarea perfecta din figura 3 s-a obtinut din bipermutarea din figura 1, aplicand mutari pe pozitiile 1, 2, 4 si 5.

Cerinta

Cunoscand o bipermutare, determinati:

  • numarul bipermutarilor perfecte distincte ce se pot obtine prin mutari;
  • numarul minim de mutari prin care se poate obtine o bipermutare perfecta;
  • o bipermutare perfecta obtinuta din bipermutarea initiala.

Date de intrare

Fişierul de intrare biperm.in contine pe prima linie valoarea lui n. Urmatoarele doua linii contin, fiecare, cate n elemente separate prin cate un spatiu, formand o bipermutare.

Date de ieşire

Fişierul de ieşire biperm.out va contine:

  • pe prima linie doua numere naturale separate printr-un spatiu, reprezentand numarul bipermutarilor perfecte distincte ce se pot obtine din bipermutarea data, respectiv numarul minim de mutari prin care se poate obtine o bipermutare perfecta;
  • pe urmatoarele doua linii se vor tipari cate n numere separate prin spatiu, reprezentand o bipermutare perfecta obtinuta din bipermutarea data.

Restricţii

  • 2 < n ≤ 10 000
  • calculul corect al numarului bipermutarilor perfecte distincte valoreaza 30% din punctaj.
  • calculul corect al numarului minim de mutari valoreaza 10% din punctaj.
  • tiparirea unei bipermutari perfecte valoreaza 60% din punctaj. Pot exista mai multe solutii, se va admite orice solutie corecta.
  • se garanteaza ca numarul bipermutarilor perfecte distincte nu depaseste 2 000 000 000 pentru niciun test.
  • acordarea punctajului la un raspuns corect este conditionata de existenta raspunsurilor anterioare, indiferent de corectitudinea lor.
  • pentru 40% din teste n ≤ 20
  • pentru 40% din teste 20 < n ≤ 400
  • pentru 20% din teste 400 < n ≤ 10 000

Exemplu

biperm.inbiperm.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 permutari perfecte. Numarul minim de mutari este 1 si exista doua solutii cu numr minim de mutari:
1 2 5 3 4
3 5 2 4 1
si
1 5 2 3 4
3 2 5 4 1
Celelalte doua solutii, ce nu se obtin din numar minim de mutari sunt:
3 2 5 4 1
1 5 2 3 4
si
3 5 2 4 1
1 2 5 3 4
Pentru a treia cerinta oricare dintre cele 4 solutii este acceptata.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content