Fişierul intrare/ieşire:triunghi5.in, triunghi5.outSursăOJI 2014 - clasa a 10-a
AutorZoltan SzaboAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Triunghi5

Gigel este un pasionat al triunghiurilor. El colectează beţişoare de diferite lungimi şi le asamblează în diferite triunghiuri. Ieri, el avea 6 beţişoare de lungimi 5, 2, 7, 3, 12 şi 3. Din aceste beţişoare, Gigel a construit un triunghi de laturi 3, 3 şi 5, iar beţişoarele de lungimi 2, 7, 12 au rămas nefolosite pentru că aceste lungimi nu pot forma laturile unui triunghi.
Din acest motiv, Gigel s-a hotărât să facă o colecţie de beţişoare, dintre care oricum ar alege 3 elemente, acestea să nu poată forma laturile unui triunghi, proprietate pe care o vom numi în continuare proprietate anti-triunghi. Gigel, pornind de la setul iniţial de lungimi 2, 7, 12 s-a gândit la două metode de realizare a unei colecţii de 5 beţişoare cu proprietatea anti-triunghi, şi anume:

  • Păstrează cel mai scurt beţişor, cel de lungime 2, şi creează un set nou adăugând alte beţişoare de lungime mai mare sau egală cu cel iniţial. De exemplu, următoarele 5 lungimi sunt corecte: 2, 2, 12, 50, 30 .
  • Păstreză toate beţişoarele, şi anume 2, 7, 12, pe care le va completa cu alte beţişoare de diferite lungimi (mai scurte sau mai lungi), astfel ca proprietatea anti-triunghi să se păstreze. Următoarele 5 lungimi respectă proprietatea anti-triunghi: 2, 7, 12, 4, 1.

Cerinta

Cunoscând un şir de n numere naturale nenule a1,a2,...,an având proprietatea anti-triunghi, şi un număr k (k > n), se cere să construiţi un şir de k numere naturale având proprietatea anti-triunghi, în conformitate cu una dintre următoarele două restricţii:

  • Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
  • Printre cele k elemente ale şirului construit se regăsesc toate elementele şirului iniţial.

Date de intrare

Fişierul de intrare triunghi.in conţine pe prima linie valorile numerelor v, n şi k, separate prin spaţiu. Linia următoare conţine n numere naturale separate prin spaţiu, ce formează un şir cu propietatea anti-triunghi.

Date de ieşire

În fişierul de ieşire triunghi5.out va conţine k numere pe o singură linie.
Dacă valoarea lui v este 1, atunci fişierul va conţine k numere naturale cu proprietatea anti-triunghi, separate prin spaţiu, în care cel mai mic element este identic cu minimul şirului dat în fişierul de intrare.
Dacă valoarea lui v este 2, atunci fişierul va conţine k numere naturale cu proprietatea anti-triunghi, separate prin spaţiu, printre care se regăsesc toate elementele şirului iniţial.

Restricţii

  • 3 ≤ n < k ≤ 46
  • 1 ≤ lungimea unui beţişor ≤ 2.000.000.000
  • Pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte, iar pentru cerinţa a doua se acordă 70 de puncte
  • Se garantează că întotdeauna există soluţie.
  • Soluţia nu este unică - se admite orice răspuns corect.

Exemplu

triunghi5.intriunghi5.outExplicatii
1 3 5
7 2 12
2 2 30 50 12
v=1, n=3, k=5. În varianata 1 avem de tipărit 5 numere, valoarea minimului este 2 în ambele şiruri.
2 3 5
7 2 12
1 4 12 7 2
v=2, n=3, k=5. În varianata 2 printre elementele şirului tipărit se regăsesc toate elementele şirului iniţial.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?