Fişierul intrare/ieşire:perechi.in, perechi.outSursăONI 2016 clasa a 5-a
AutorDan PracsiuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.7 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Perechi (clasa a 5-a)

Fie un şir a1, a2, ..., an 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 a1, a2, ..., an.

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 ai şi la aj (unde i şi j sunt distincte şi sunt cuprinse între 1 şi n).

Restricţii

  • 5 ≤ n < 2000, n este impar
  • 0 ≤ ai ≤ 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

perechi.inperechi.outExplicaţie
1
5
8 2 8 8 2
2 5 6
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.
2
5
8 5 6 3 10
1 2 2
3 4 4
2 4 3
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
1
5
8 2 7 8 2
0
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.
2
3
1 2 3
1 3 1
1 2 2
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici