.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » bubblesort

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
bubblesort


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
16MB / 2MB

Miruna a învăţat recent la ora de informatică algoritmul bubblesort. 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.

Exemple

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

autor: Stud. Andrei Grigorean
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor