Fișierul intrare/ieșire	perechi.in, perechi.out	Sursă	ONI 2016 clasa a 5-a
Autor	Dan Pracsiu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.25 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	4.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Perechi (clasa a 5-a)

Fie un șir a₁, a₂, ..., a_n de numere naturale, unde n este impar. Avem la dispoziție o singură operație admisă și
anume: putem aduna la două poziții diferite din șir o aceeași valoare naturală nenulă.

Cerințe

1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
2. Folosind de mai multe ori operația admisă, să se obțină șirul cu toate elementele egale, dar valoarea egală obținută
   să nu depășească dublul valorii maxime din șirul inițial.

Date de intrare

Fișierul de intrare perechi.in conține pe prima linie un număr natural C, pe a doua linie numărul n, iar pe linia a treia,
separate prin câte un spațiu, valorile a₁, a₂, ..., a_n.

Date de ieșire

Fișierul perechi.out va conține:

1. Dacă C=1, atunci se va rezolva doar prima cerință, deci se va afișa pe prima linie valoarea 0 dacă nu se pot obține
   în șir toate elementele egale, sau se vor afișa trei numere naturale i j v cu semnificația: la pozițiile i și j din șir se
   adaugă valoarea v și astfel toate elementele vectorului vor deveni egale.
2. Dacă C=2, atunci se va rezolva doar a doua cerință. Pe fiecare linie a fișierului de ieșire se vor afișa exact trei valori
   i j v cu semnificația: se adună valoarea v la a_i și la a_j (unde i și j sunt distincte și sunt cuprinse între 1 și n).

Restricții

• 5 ≤ n < 2000, n este impar
• 0 ≤ a_i ≤ 100 000 000, pentru orice i=1..n
• Elementele șirului inițial nu sunt neapărat distincte, dar nu sunt nici toate egale
• Dacă există mai multe soluții, puteți afișa oricare dintre ele.
• Dacă numărul operațiilor aplicate este mai mic sau egal decât n, iar valoarea finală este de cel mult două ori cât
  maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 100% din
  punctaj.
• Dacă numărul operațiilor este cuprins între n+1 și 2n, iar valoarea finală este de cel mult două ori cât maximul
  inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 70% din punctaj.
• Dacă numărul operațiilor este mai mare de 2n sau dacă valoarea finală depășește dublul valorii maxime inițiale,
  atunci veți primi 0 puncte. De asemenea, dacă în urma operațiilor aplicate nu se obține un șir cu aceeași valoare
  peste tot, sau dacă aplicați o operație în care pozițiile i și j nu sunt din intervalul 1..n, atunci de asemenea veți
  primi 0 puncte.
• Pentru teste valorând 20 de puncte vom avea C=1. Pentru restul testelor vom avea C=2, din care pentru 30 de
  puncte șirul va fi format din numere distincte cuprinse între 1 și n.

Exemple