Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-09-14 12:51:18.
Revizia anterioară   Revizia următoare  

 

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 memorie54663 kbytes
Scorul tăuN/ADificultateN/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.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?