bubblesort

Bubblesort

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

Poveste şi cerinţă...

Miruna a învăţat recent la ora de informatică algoritmul $bubble sort$. Mai jos puteţi vedea codul algoritmului în limbajul $C++$:
== code(cpp) |
int steps = 0;
while (true) {
    ++steps;
    bool isSorted = true;
    for (int i = 1; i < n; ++i)
        if (v[i] > v[i + 1]) {
             swap(v[i], v[i + 1]);
             isSorted = false;
        }
    if (isSorted) break;
}
==
Miruna defineşte ordinul unei permutări ca fiind egal cu numărul de paşi necesari algoritmului pentru a sorta permutarea (adică valoarea variabilei $steps$ în codul de mai sus la sfârşitul execuţiei).
 
h2. Cerinţă
 
Dându-se trei numere naturale $N$, $M$ şi $K$ aflaţi care este cea de a $K$-a permutare în ordine lexicografică de lungime $N$ şi ordin $M$.

h2. Date de intrare

Fişierul de intrare $bubblesort.in$ ...

Pe prima linie a fişierului de intrare $bubblesort.in$ se vor afla trei numere naturale $N$, $M$ şi $K$, având semnificaţia de mai sus.
 

h2. Date de ieşire

În fişierul de ieşire $bubblesort.out$ ...

Pe prima linie a fişierului de ieşire $bubblesort.out$ veţi afişa N numere naturale despărţite prin spaţiu reprezentând permutarea cerută.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 300$
* $1 ≤ M ≤ N$
* Se garantează existenţa soluţiei pe datele de test.

h2. Exemplu
table(example). |_. bubblesort.in |_. bubblesort.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 4 123
| 1 5 3 6 2 4 7

|

 
h3. Explicaţie
 
...

table(example).
| 20 5 1097525229548
| 2 7 1 3 4 6 5 10 13 11 9 8 15 12 19 17 16 14 20 18
|

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

4905