| Fişierul intrare/ieşire: | selectie.in, selectie.out | Sursă | Cerc informatică Vianu |
| Autor | Din Folclor | Adăugată de |  Teodor Plop •teodor94 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Selecţie (clasa a 6-a)
Notă: aceasta este o problemă didactică. Scopul ei este de a învăţa să implementaţi algoritmul quickselect şi, implicit, algoritmul quicksort, care foloseşte acelaşi pas de pivotare. Nu vă furaţi singuri căciula apelînd funcţia de bibliotecă nth_element().
Dat un şir de N numere şi o poziţie K în acel şir să se spună ce element s-ar afla pe acea poziţie dacă şirul ar fi sortat.
Date de intrare
Fişierul de intrare selectie.in conţine pe prima linie două numere naturale N şi K cu semnificaţia din enunţ. Pe următoarele N linii se află câte un număr natural, element al şirului.
Date de ieşire
În fişierul de ieşire selectie.out se va afla un singur număr, elementul care s-ar afla pe poziţia K dacă şirul ar fi sortat.
Restricţii
- 1 ≤ K ≤ N ≤ 1.000.000
- 1 ≤ v[i] ≤ 1.000.000.000, unde v[i] este un element al şirului.
Exemplu
| selectie.in | selectie.out |
|---|---|
| 7 5 1 3 7 2 5 4 3 | 4 |
Explicaţie
Şirul sortat este: 1 2 3 3 4 5 7. Cel de-al cincilea element este 4.
