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 de 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 reprezentate prin 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 de 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 destul de 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] din permutarea ceruta.

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 separate prin cate un spatiu.

Restricţii

• N este putere de 2
• 1 ≤ M ≤ 10 000

• Subtask 1 (1 puncte): N = 1 (Feedback testul 1)
• Subtask 2 (1 puncte): N = 2 (Feedback testul 2)
• Subtask 3 (1 puncte): N = 4 (Feedback testul 3)
• Subtask 4 (2 puncte): N = 8 (Feedback testul 4)
• Subtask 5 (5 puncte): N = 16 (Feeback testul 5)

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

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?