Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | triangles.in, triangles.out | Sursă | Infoarena Monthly 2012, Runda 8 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Ionescu Vlad •vladii |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 54663 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Triangles
 Aceasta problema este sponsorizata de IXIA! Participantul inscris care va obtine cel mai mare punctaj va primi un premiu din partea sponsorului nostru. |
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.
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 despartite prin cate un spatiu, reprezentand sirul de numere pe care il detine Marian.
Date de ieşire
Î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.
Restricţii
- 3 ≤ N ≤ 2.000.002
- 3 ≤ K ≤ 5.000
- Numerele din sir vor fi numere naturale cuprinse in intervalul [1, 109]
- 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.
Exemplu
| triangles.in | triangles.out |
|---|---|
| 5 3 3 2 1 2 3 | 1 2 5 |
Explicaţie
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.
