Fișierul intrare/ieșire perechi.in, perechi.out Sursă ONI 2016 clasa a 5-a
Autor Dan Pracsiu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.7 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in perechi.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii