Fişierul intrare/ieşire:triangles.in, triangles.outSursăInfoarena Monthly 2012, Runda 8
AutorRadu Stefan VoroneanuAdăugată devladiiIonescu Vlad vladii
Timp execuţie pe test0.2 secLimită de memorie50567 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Triangles

Aceasta problema a fost sponsorizata de IXIA in runda round_id! Participantul care a castigat premiul este scipianusFMI Ciprian Olariu 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.

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.intriangles.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content