1512 - Mars

Cerinţa

Se consideră un tablou unidimensional cu n elemente numere întregi, numerotate de la 1 la n, inițial toate nule. Asupra tabloului se fac m operații s d X cu semnificația: toate elementele cu indici cuprinși între s și d își măresc valoarea cu X.

Să se afișeze tabloul după realizarea celor m operații.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi m triplete s d X, cu semnificația din enunț.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou n elemente ale tabloului, separate prin exact un spațiu, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ n ≤ 200.000
1 ≤ m ≤ 200.000
1 ≤ s ≤ d ≤ n
-1000 ≤ X ≤ 1000

Exemplu 1

Intrare: 10 6; 8 10 2; 3 10 -3; 5 9 7; 5 5 5; 6 7 2; 1 1 -1
Ieșire: Datele sunt introduse correct; -1 0 -3 -3 9 6 6 6 6 -1

Exemplu 2

Intrare: 10 6 1 1; 8 10 2; 3 10 -3; 5 9 7; 5 5 5 2 3; 6 7 2 9 0; 1 1 -1 2 3 5
Ieșire: Datele nu corespund restricțiilor impuse.; -1 0 -3 -3 9 6 6 6 6 -1

Rezolvare

Rezolvare ver. 1

1512 - Mars

def citire_date():

   n, m = map(int, input().split())
   op = []
   for i in range(m):
       s, d, X = map(int, input().split())
       op.append((s, d, X))
   return n, m, op

def aplicare_operatii(n, m, op):

   v = [0] * n
   for s, d, X in op:
       if s > n or d > n or s < 1 or d < 1 or s > d or abs(X) > 1000:
           print("Datele nu corespund restricțiilor impuse.")
           return
       for i in range(s-1, d):
           v[i] += X
   print("Datele sunt introduse corect.")
   print(*v)

if __name__ == '__main__':

   n, m, op = citire_date()
   aplicare_operatii(n, m, op)

</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input() primește datele de intrare de la utilizator și returnează n, m și tabloul inițial. Funcția update_array() primește un tablou arr, o pereche de indici s și d și o valoare X, și actualizează toate elementele din arr cu indici cuprinși între s și d astfel încât să fie adăugate la ele valoarea X. Funcția solve() primește n, m și tabloul inițial, iterează prin cele m operații și actualizează tabloul conform operațiilor. Funcția validate() verifică dacă tabloul rezultat are lungimea corectă. În if __name__ == '__main__', apelăm funcțiile în ordine pentru a rezolva problema și afișăm tabloul rezultat.