| Fișierul intrare/ieșire | selectie.in, selectie.out | Sursă | Cerc informatică Vianu |
|---|---|---|---|
| Autor | din folclor | Adăugată de |
Teodor Plop
•
teodor94
|
| Timp de execuție pe test | 0.75 sec | Limită de memorie | 8192 KB |
| Scorul tău | N/A | Dificultate |
  3
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.
