Fişierul intrare/ieşire:ultimulcartus.in, ultimulcartus.outSursăJunior Challenge 2016
AutorAndrei ConstantinescuAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 ai si se va cere pentru fiecare element ai sa se afiseze valoarea P[ai] 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[ai] 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

ultimulcartus.inultimulcartus.out
2
2
1 2
1
1
2 1

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?