Fişierul intrare/ieşire:cheerleader.in, cheerleader.outSursăInfo(1)cup 2020
AutorAlexa Tudose, Tamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima •tamionv
Timp execuţie pe test1.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cheerleader

Majoretele din şcoala lui Pătrăţel au hotărât să creeze o nouă manifestaţie artistică pentru cupa de Fo(1)tbal a şcolii. Sunt 2N majorete, fiecare cu înălţimi distincte între 0 şi 2N - 1. Majoretele stau într-o linie. Înalţimea majoretei care este iniţial la pozitia i este h[i] pentru 1 ≤ i ≤ 2N.

Majoretele ştiu doua manevre sincronizate de dans:

  • Marele swap. În manevra aceasta, primele 2N-1 majorete fac schimb de locuri cu ultimele 2N-1 majorete.
  • Marele split. În manevra aceasta, majoretele situate la poziţii impare se duc la începutul rândului, si cele situate la poziţii pare se duc la sfârşitul rândului.

De exemplu, un mare swap efectuat de majoretele A, B, C, D, E, F, G, H va rezulta in randul E, F, G, H, A, B, C, D, şi un mare split efectuat de aceleasi majorete rezulta in randul A, C, E, G, B, D, F, H.

Definim numărul de inversiuni ale unui rând de majorete cu înălţimile h'[1], ..., h'[2N] ca fiind numărul de perechi (i, j), 1 ≤ i < j ≤ 2^N unde h'[i] > h'[j]. Majoretele vor să găsească o secvenţă de manevre care minimizeaza numărul de inversiuni ale rândului rezultant.

Fisier de intrare

Pe prima linie a fisierului de intrare cheerleader.in veţi găsi numărul întreg N.
Pe a doua linie a fisierului de intrare veţi găsi 2N numere întregi ce reprezintă h[1], ..., h[2N].

Fisier de iesire

Pe primul rând al fisierului de iesire cheerleader.out se va afla numărul minim de inversiuni.
Pe al doilea rând al outputului se va afla un şir de caractere ce reprezintă o secvenţă de manevre care conduce la numărul minim de inversiuni. Un caracter 1 va reprezenta un mare swap, iar un caracter 2 va reprezenta un mare split. Orice secvenţă de manevre care duce la numărul minim de inversiuni va fi acceptată.

Restrictii

  • 0 ≤ N ≤ 17.
  • N poate fi 0.
  • Lungimea secvenţei de manevre trebuie să fie de cel mult 500.000.
  • Pentru 16 puncte, N ≤ 4
  • Pentru 10 puncte, N ≤ 7
  • Pentru 25 puncte, N ≤ 11
  • Pentru 21 puncte, N ≤ 16, se garantează că numărul minim de inversiuni ce poate fi obţinut este 0.

Exemple

cheerleader.incheerleader.out
2
0 3 1 2
1
2212
3
2 3 7 6 1 4 5 0
8
21221
4
1 4 8 5 3 6 12 13 10 11 2 9 14 0 15 7
43
2222
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?