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, pe care justitia l-a achitat 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 data

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;
    }
}

Date de intrare

Fişierul de intrare ultimulcartus.in ...

Date de ieşire

În fişierul de ieşire ultimulcartus.out ...

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?