== include(page="template/taskheader" task_id="sdo") ==

Se dă o mulţime de numere naturale $A$, de $N$ elemente şi un număr natural $K$. Să se determine a $K$-a 'statistică de ordine':http://en.wikipedia.org/wiki/Order_statistic (al $K$-lea cel mai mic element) a mulţimii.

A $i$-a 'statistică de ordine':http://en.wikipedia.org/wiki/Order_statistic a unei mulţimi este al $i$-lea cel mai mic element al mulţimi. Fiind date o mulţime de numere naturale $A$, de $N$ elemente şi un număr natural $K$, să se determine a $K$-a statistică de ordine a mulţimii.

h2. Date de intrare

Fişierul de intrare $sdo.in$ conţine pe prima linie $N$ şi $K$, iar pe a doua linie $N$ numere naturale, reprezentând elementele mulţimii.

Fişierul de intrare $sdo.in$ conţine pe prima linie $N$ şi $K$, iar pe a doua linie $N$ numere naturale, reprezentând elementele mulţimii $A$.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ K ≤ N ≤ 3 000 000$

* Toate cele $N$ numere sunt din intervalul $[1, 10^9^]$

* Toate cele $N$ elemente ale mulţimii $A$ sunt din intervalul $[1, 10^9^]$

h2. Exemplu

h3. Explicaţie

În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: $1 4 6 7 10 11 13 14$, prin urmare al 3-lea cel mai mic element este 6.

În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: $1 4 **6** 7 10 11 13 14$, prin urmare al 3-lea cel mai mic element este 6.

O primă soluţie(?), care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex>O(N^2)</tex>, şi ar trebui să obţină ... puncte.

O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină 70 puncte.

În final, 'soluţia':job_detail/369660?action=view-source care ar trebui să obţină $100$ de puncte foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $K$-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Acest algoritm este implementat şi în STL, funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, în cel mai defavorabil caz putând atinge <tex>O(N^2)</tex>

În final, 'soluţia':job_detail/369660?action=view-source care ar trebui să obţină $100$ de puncte foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $K$-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Acest algoritm este implementat şi în STL, funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, dar în cel mai defavorabil caz poate atinge <tex>O(N^2)</tex>
 
h3. Aplicaţii
 
* 'Toys':problema/toys
* 'Geometrie':problema/geom

== include(page="template/taskfooter" task_id="sdo") ==