Fişierul intrare/ieşire:bubblesort.in, bubblesort.outSursăLot Alba Iulia 2010, Baraj 2
AutorAndrei GrigoreanAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.175 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bubblesort

Miruna a învăţat recent la ora de informatică algoritmul bubble sort. Mai jos puteţi vedea codul algoritmului în limbajul C++:
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).

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.

Date de intrare

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.

Date de ieşire

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

Restricţii

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

Exemplu

bubblesort.inbubblesort.out
7 4 123
1 5 3 6 2 4 7
20 5 1097525229548
2 7 1 3 4 6 5 10 13 11 9 8 15 12 19 17 16 14 20 18
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content