Lista de probleme 10

Filtrare

Se dă un șir cu n elemente, numere întregi. Folosind metoda QuickSort, ordonați crescător elementele acestui șir.

Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort, ordonați crescător elementele acestui șir.

Se dau n numere naturale. Să se afișeze al k-lea cel mai mic element din șir.

#2525 Cioc

Cioc, un elev abia aterizat în clasa a IX-a, primește de la doamna profesor de informatică un șir de n numere naturale pe care trebuie să îl prelucreze. Astfel, băiatul trebuie să scrie după fiecare dintre cele k cele mai mici elemente dublul lor. Dacă cel mai mare dintre aceste numere se repetă și deja se depășesc cele k elemente prevăzute, doamna profesor îi dă libertatea băiatului de a modifica valoarea lui k astfel încât să cuprindă și aceste valori. De exemplu, dacă n = 7, v[] = {1, 4, 6, 2, 3, 4, 5} și k = 4, atunci, în urma prelucrării, șirul v devine {1, 2, 4, 8, 6, 2, 4, 3, 6, 4, 8, 5}, și deci \( k_{final}=5 \).

Cunoscându-se n, șirul v și k, să se afișeze:

  • Numărul \( k_{final} \);
  • Vectorul după prelucrare.

Best of CNCV / Warmup Round

Se dau înălțimile a n copii, numerotați de la 1 la n, exprimate prin numere naturale. Afișați numerele de ordine ale copiilor în ordinea crescătoare a înălțimii lor.

Pentru sortare se va folosit metoda QuickSort sau MergeSort.

#1157 KSort2

Se dă un vector cu n elemente, numere naturale și un număr k. Ordonați crescător primele k elemente ale vectorului și descrescător ultimele n-k elemente.

Pentru sortare se va folosit metoda QuickSort sau MergeSort.

Metoda Bucket Sort constă în distribuirea elementelor în mai multe grupe, numite “bucket-uri”. Apoi fiecare bucket este sortat individual folosind un algoritm de sortare oarecare.

Se consideră 2 permutări A şi B ale mulţimii {1, 2, ..., N}. Printr-o operaţie se pot selecta două elemente adiacente din B şi să se interschimbe (i.e. swap(B[i], B[i + 1]) pentru 1 ≤ i < N). Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j]. Să se determine numărul inversiunilor permutării.

Se dă un vector cu n elemente numere întregi nenule.
Să se ordoneze crescător subșirul format din elementele negative din vector și descrescător subșirul format din elementele pozitive.