Fişierul intrare/ieşire:	ultimulcartus.in, ultimulcartus.out	Sursă	Junior Challenge 2016
Autor	Andrei Constantinescu	Adăugată de	JuniorChallenge2016 •JuniorChallenge2015
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ultimul Cartus

Spoiler alert! Dupa moartea lui Miclovan viata a devenit monotona si absenta, comisarul Roman este pus in situatia de a il prinde pe Semaca, anticarul proaspat achitat de justitie din lipsa de probe.

Astfel, Roman ajunge in fata unei arhive vechi, plina cu N dosare (N putere a lui 2), aranjate intr-o ordine aleatorie. Un prim pas in analizarea acestora il reprezinta ordonarea lor alfabetica dupa titlu. Vom considera pentru simplitate ca titlurile celor N dosare sunt numere naturale distincte, cuprinse intre 1 si N (altfel spus, ordinea dosarelor reprezinta o permutare a numerelor de la 1 la N).

Deoarece numarul dosarelor este destul de mare, Roman propune o abordare sistematica, pe care o va duce la bun sfarsit cu ajutorul subordonatilor sai. Aceasta poate fi descrisa prin urmatorul algoritm:

const int NMAX = 1000000000;

int N;
int p[NMAX + 1]; //Permutarea

int ops;
void bubble(int gap) {
    bool ok = true;
    while (ok) {
        ok = false;
        for (int i = 1; i <= N - gap; ++ i)
            if (p[i] > p[i + gap]) {
                swap(p[i], p[i + gap]);
                ++ ops;
                ok = true;
            }
    }
}

void bubblesort() {
    int gap = N;
    while (gap) {
        bubble(gap);
        gap /= 2;
    }
}

Mai exact, procedura lui Roman este un singur apel al functiei bubblesort().
Dupa imediata ordonare a dosarelor Roman isi pune o intrebare existentiala "Care e cea mai mare valoare posibila a variabilei ops pentru o permutare oarecare?"

Cerinta

Dandu-se N, numar natural nenul, putere a lui 2, sa se calculeze urmatoarele

1. Valoarea maxima posibila a variabilei ops dupa un singur apel al functiei bubblesort();
2. Numarul de permutari cu N elemente pentru care se atinge acest maxim;
3. Dintre acestea, permutarea minima din punct de vedere lexicografic. Deoarece output-ul poate fi prea mare, se va da un un sir cu M elemente a_i si se va cere pentru fiecare element a_i sa se afiseze valoarea p[a_i].

Date de intrare

Pe prima linie a fişierului de intrare ultimulcartus.in se va afla numarul N.
Pe a doua linie a fiserului de intrare se va afla numarul M.
Pe a treia linie a fisierului de intrare va fi sirul a, cu elementele separate prin spatii.

Date de ieşire

Fişierului de ieşire ultimulcartus.out va contine 3 linii, cate una pentru fiecare cerinta. Pentru cerinta 3 valorile p[a_i] se vor afisa toate pe aceeasi linie, oricare doua consecutive fiind separate prin cate un spatiu.

Restricţii

• N este putere a lui 2
• 1 ≤ M ≤ 10 000

• Subtask 1 (1 puncte): N = 1
• Subtask 2 (1 puncte): N = 2
• Subtask 3 (1 puncte): N = 3
• Subtask 4 (2 puncte): N = 4
• Subtask 5 (5 puncte): N = 5

• Subtask 6 (20 puncte): 1 ≤ N ≤ 3 000
• Subtask 7 (35 puncte): 1 ≤ N ≤ 1 000 000
• Subtask 8 (35 puncte): 1 ≤ N ≤ 1 000 000 000

Exemplu

Explicaţie

Exista doar 2 permutari de 2 elemente, 1 2 si 2 1, ale caror valori ops corespunzatoare sunt 0 si, respectiv, 1.

Cum se trimit solutii?