Pls Traian intră în concurs | perechi

This was the problem page during the contest. Access the current page here.
Time limit: 0.06s Memory limit: 64MB Input: perechi.in Output: perechi.out

Fie un şir a1a_1, a2a_2, ......, ana_n de numere naturale, unde nn 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 CC, pe a doua linie numărul nn, iar pe linia a treia, separate prin câte un spațiu, valorile a1a_1, a2a_2, ......, ana_n.

Date de ieşire

Fişierul perechi.out va conţine:

  1. Dacă C=1C = 1, atunci se va rezolva doar prima cerință, deci se va afișa pe prima linie valoarea 00 dacă nu se pot obține în șir toate elementele egale, sau se vor afișa trei numere naturale i j vi \ j \ v cu semnificația: la pozițiile ii și jj din șir se adaugă valoarea vv și astfel toate elementele vectorului vor deveni egale.
  2. Dacă C=2C = 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 vi \ j \ v cu semnificația: se adună valoarea vv la aia_i și la aja_j (unde ii și jj sunt distincte și sunt cuprinse între 11 și nn).

Restricţii și precizări

  • 5n<2 0005 \leq n \lt 2 \ 000, nn este impar
  • 0ai100 000 0000 \leq a_i \leq 100 \ 000 \ 000, pentru orice 1in1 \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 nn, 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%100\% din punctaj.
  • Dacă numărul operațiilor este cuprins între n+1n+1 și 2n2 \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%70\% din punctaj.
  • Dacă numărul operațiilor este mai mare de 2n2n sau dacă valoarea finală depășește dublul valorii maxime inițiale, atunci veți primi 00 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 ii și jj nu sunt din intervalul 1...n1 ... n, atunci de asemenea veți primi 00 puncte.
  • Pentru teste valorând 2020 de puncte vom avea C=1C = 1. Pentru restul testelor vom avea C=2C = 2, din care pentru 3030 de puncte șirul va fi format din numere distincte cuprinse între 11 și nn.

Exemplul 1

perechi.in

1
5
8 2 8 8 2

perechi.out

2 5 6

Explicație

C=1C = 1, deci se va rezolva doar prima cerință! Adunând valoarea 66 la pozițiile 22 și 55 se va obține șirul constant 88, 88, 88, 88, 88.

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=2C = 2, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este 1010, deci valoarea finală trebuie să fie maximum 2020. Trebuie efectuate cel mult 55 operații pentru 100100 puncte.
Aplicând operația 11, 22, 22 obținem șirul 1010, 77, 66, 33, 1010
Aplicând operația 33, 44, 44 obținem șirul 1010, 77, 1010, 77, 1010
Aplicând operația 22, 44, 33 obținem șirul 1010, 1010, 1010, 1010, 1010

Exemplul 3

perechi.in

1
5
8 2 7 8 2

perechi.out

0

Explicație

C=1C = 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=2C = 2, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este 33, deci valoarea finală trebuie să fie maximum 66. Trebuie efectuate cel mult 33 operații pentru 100100 puncte.
Aplicând operația 11, 33, 11, obținem șirul 22, 22, 44
Aplicând operația 11, 22, 22, obținem șirul 44, 44, 44

Log in or sign up to be able to send submissions!