triangles

Triangles

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

Fiind un baiat descurcaret, Marian are parte de foarte multe numere (uneori atit de multe, incat nu le poate face fata: aproximativ $10$ milioane). Asa ca, datorita marei sale pasiuni pentru geometrie si triunghiuri reflectorizante, a compus urmatoarea problema pe care voi trebuie sa o rezolvati: se da un sir de $N$ numere naturale si trebuie sa alegeti exact $K$ dintre acestea, astfel incat oricare $3$ numere dintre cele $K$ alese sa poata fi laturile unui triunghi.

== include(page="template/ixia-winner" round="8" user_id="scipianus") ==
 
Fiind un baiat descurcaret, Marian are parte de foarte multe numere (uneori atit de multe, incat nu le poate face fata: aproximativ $2$ milioane si inca vreo 2). Asa ca, datorita marei sale pasiuni pentru geometrie si triunghiuri reflectorizante, a compus urmatoarea problema pe care voi trebuie sa o rezolvati: se da un sir de $N$ numere naturale si trebuie sa alegeti exact $K$ dintre acestea, astfel incat oricare $3$ numere dintre cele $K$ alese sa poata fi laturile unui triunghi.

h2. Date de intrare

Fişierul de intrare $triangles.in$ contine pe prima linie $2$ numere naturale $N$ si $K$, separate prin cate un spatiu. Pe a doua linie se vor afla $N$ numere naturale desparite prin cate un spatiu, reprezentand sirul de numere pe care il detine Marian.

Fişierul de intrare $triangles.in$ contine pe prima linie $2$ numere naturale $N$ si $K$, separate prin cate un spatiu. Pe a doua linie se vor afla $N$ numere naturale despartite prin cate un spatiu, reprezentand sirul de numere pe care il detine Marian.

h2. Date de ieşire

În fişierul de ieşire $triangles.out$ se vor afla pe prima linie $K$ numere naturale desparite prin cate un spatiu, reprezentand numerele alese din sirul dat de $N$ elemente.

În fişierul de ieşire $triangles.out$ se vor afla pe prima linie $K$ numere naturale despartite prin cate un spatiu, reprezentand indicii (primul element din sir are indicele $1$) numerelor alese din sirul dat de $N$ elemente.

h2. Restricţii

* $3 ≤ N ≤ 10.000.000$
* $3 ≤ K ≤ 16.000$
* Numerele din sir vor fi numere naturale cuprinse in intervalul [1, 10^9]
* Daca exista mai multe moduri de alegere a numerelor, se poate afisa oricare dintre ele

* $3 ≤ N ≤ 2.000.002$
* $3 ≤ K ≤ 5.000$
* Numerele din sir vor fi numere naturale cuprinse in intervalul [$1$, $10^9^$]
* Triunghiurile formate de numere pot fi si degenerate
* Indicii se pot afisa in orice ordine
* Daca exista mai multe moduri de alegere a numerelor, se poate alege oricare dintre ele

* Se garanteaza ca exista solutie.
h2. Exemplu

table(example). |_. triangles.in |_. triangles.out |
| 5 3
  3 2 1 2 3

| 2 3 3

| 1 2 5

|
h3. Explicaţie

Alte alegeri erau corecte de asemenea, spre exemplu: $1 2 2$ sau $2 2 3$.

Numerele $3 2 3$ pot fi laturile unui triunghi, iar aceste numere au (o posibilitate) indicii $1 2 5$. Alte alegeri erau corecte de asemenea, spre exemplu (indicii): $2 3 4$ sau $2 4 5$.

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

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

8375