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:
1. 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.
2. 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.
Cerinţă
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:
Varianta 1. Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
Varianta 2. Printre cele k elemente ale şirului construit se regăsesc toate elementele şirului iniţial.
Date de intrare
Fişierul de intrare triunghi6.in conţine pe prima linie valorile numerelor v n 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
Fişierul de ieşire triunghi6.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.
Exemple
triunghi6.in
triunghi6.out
Explicaţii
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 varianta 2 printre elementele şirului tipărit se regăsesc toate elementele şirului iniţial.
