Pls Traian intră în concurs | perechi

Fie un şir $a_1$, $a_2$, $...$, $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 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_1$, $a_2$, $...$, $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 și precizări

• $5 \leq n \lt 2 \ 000$, $n$ este impar
• $0 \leq a_i \leq 100 \ 000 \ 000$, pentru orice $1 \leq i \leq 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 $2 \cdot 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 $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$.

Exemplul 1

perechi.in

1
5
8 2 8 8 2

perechi.out

2 5 6

Explicație

$C = 1$, deci se va rezolva doar prima cerință! Adunând valoarea $6$ la pozițiile $2$ și $5$ se va obține șirul constant $8$, $8$, $8$, $8$, $8$.

Exemplul 2

perechi.in

2
5
8 5 6 3 10

perechi.out

1 2 2
3 4 4
2 4 3

Explicație

$C = 2$, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este $10$, deci valoarea finală trebuie să fie maximum $20$. Trebuie efectuate cel mult $5$ operații pentru $100$ puncte.
Aplicând operația $1$, $2$, $2$ obținem șirul $10$, $7$, $6$, $3$, $10$
Aplicând operația $3$, $4$, $4$ obținem șirul $10$, $7$, $10$, $7$, $10$
Aplicând operația $2$, $4$, $3$ obținem șirul $10$, $10$, $10$, $10$, $10$

Exemplul 3

perechi.in

1
5
8 2 7 8 2

perechi.out

0

Explicație

$C = 1$, deci se va rezolva doar prima cerință! Nu se poate efectua o singură operație astfel încât toate elementele șirului să devină egale.

Exemplul 4

perechi.in

2
3
1 2 3

perechi.out

1 3 1
1 2 2

Explicație

$C = 2$, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este $3$, deci valoarea finală trebuie să fie maximum $6$. Trebuie efectuate cel mult $3$ operații pentru $100$ puncte.
Aplicând operația $1$, $3$, $1$, obținem șirul $2$, $2$, $4$
Aplicând operația $1$, $2$, $2$, obținem șirul $4$, $4$, $4$