1696 - Perechi 2

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ța

Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
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 perechi2.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 de ieșire perechi2.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 ≤ 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.

Exemplul 1

perechi2in.txt

1

5

8 2 8 8 2

perechi2out.txt

2 5 6

Exemplul 2

perechi2in.txt

2

5

8 5 6 3 10

perechi2out.txt

1 2 2

3 4 4

2 4 3

Rezolvare

<syntaxhighlight lang="python" line>

1. 1696 - Perechi 2

def pot_deveni_egale(n, arr):

   elemente_unice = set(arr)
   if len(elemente_unice) == 1:
       return True

   valoare_maxima = max(arr)
   contor_maxim = arr.count(valoare_maxima)

   if contor_maxim % 2 == 0:
       return True
   elif contor_maxim > 1:
       return valoare_maxima * 2 <= max(arr)
   else:
       return False

def aplicare_operatii(n, arr):

   operatii = []
   valoare_maxima = max(arr)

   for i in range(n):
       if arr[i] != valoare_maxima:
           diferenta = valoare_maxima - arr[i]
           operatii.append((i + 1, (i + 1) % n + 1, diferenta))
           arr[i] += diferenta
           arr[(i + 1) % n] += diferenta

   return operatii

def verificare_restrictii(numar): # funcția de verificare a datelor de intrare

   if 5 <= numar < 2000    # adăugăm restricția pentru n
      0 <= a[i] <= 1.000.000.000:
       return True
   else:
       return False

def main():

   with open("perechi2.in", "r") as file_in:
       C = int(file_in.readline().strip())
       n = int(file_in.readline().strip())
       arr = list(map(int, file_in.readline().split()))

   if C == 1:
       rezultat = 0 if pot_deveni_egale(n, arr) else 1
       with open("perechi2.out", "w") as file_out:
           file_out.write(str(rezultat))
   elif C == 2:
       operatii = aplicare_operatii(n, arr)
       with open("perechi2.out", "w") as file_out:
           file_out.write(str(len(operatii)) + "\n")
           for op in operatii:
               file_out.write(f"{op[0]} {op[1]} {op[2]}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>