Ultimul Cartus

ultimulcartus

== include(page="template/taskheader" task_id="ultimulcartus") ==

!>problema/ultimulcartus?roman.jpg!

*Spoiler alert!* Dupa moartea lui Miclovan viata a devenit monotona si absenta, comisarul Roman este pus in situatia de a il prinde pe Semaca, pe care justitia l-a achitat din lipsa de probe.

**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:

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:

== code(cpp) |
const int NMAX = 1000000000;
int N;

int P[NMAX + 1]; //Permutarea

int p[NMAX + 1]; // = permutarea data

int ops;

void Bubble(int gap) {

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]);

            if (p[i] > p[i + gap]) {
                swap(p[i], p[i + gap]);

                ++ ops;
                ok = true;
            }
    }
}

void BubbleSort() {

void bubblesort() {

    int gap = N;
    while (gap) {

        Bubble(gap);

        bubble(gap);

        gap /= 2;
    }
}
==

Mai exact, procedura lui Roman este reprezentata de un singur apel al procedurii $bubblesort()$.
Dupa rapida ordonare a dosarelor, Roman isi pune o intrebare existentiala "Care e valoarea maxima a variabilei $ops$ pentru o

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?"

h2. Cerinta

Dandu-se $N$, numar natural nenul, putere de 2, sa se calculeze urmatoarele:

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

# Valoarea maxima posibila a variabilei $ops$ dupa un singur apel al functiei $BubbleSort()$;
# Numarul de permutari cu $N$ elemente pentru care se atinge acest maxim;
# 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.

# Valoarea maxima a variabilei $ops$ dupa un apel al procedurii $bubblesort()$
# Numarul de permutari cu $N$ elemente pentru care se atinge acest maxim
# Dintre acestea, permutarea minima din punct de vedere lexicografic. Deoarece output-ul ar 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~}]$

h2. 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.

Pe a doua linie a fiserului de intrare se va afla numarul natural $M$.
Pe a treia linie a fisierului de intrare va fi sirul $a$, cu elementele consecutive separate prin cate un spatiu.

h2. 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.

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 pe aceasi linie, oricare doua consecutive fiind separate prin cate un spatiu.

h2. 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$)

* $1 ≤ N ≤ 1 000 000 000$ ($N$ este putere a lui $2$).
* $1 ≤ M ≤ 10000$

h2. Exemplu

  1 2
| 1
  1

  2 1

  1 2

|
h3. Explicaţie

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

...

== include(page="template/taskfooter" task_id="ultimulcartus") ==