Fişierul intrare/ieşire:	cheerleader.in, cheerleader.out	Sursă	Info(1)cup 2020
Autor	Alexa Tudose, Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/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 2^N majorete, fiecare cu înălţimi distincte între 0 şi 2^N - 1. Majoretele stau într-o linie. Înalţimea majoretei care este iniţial la pozitia i este h[i] pentru 1 ≤ i ≤ 2^N.

Majoretele ştiu doua manevre sincronizate de dans:

• Marele swap. În manevra aceasta, primele 2^N-1 majorete fac schimb de locuri cu ultimele 2^N-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'[2^N] 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 2^N numere întregi ce reprezintă h[₁], ..., h[2^N].

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

Cum se trimit solutii?