1512 - Mars

Sursa: 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

5 5 1 1

1 5 1

1 5 2

1 5 3

1 5 4

1 5 5

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 1512 - Mars

def validare(n, m, operatii):

   if not (1 <= n <= 200000) or not (1 <= m <= 200000):
       return False
   for op in operatii:
       if not (1 <= op[0] <= op[1] <= n) or not (-1000 <= op[2] <= 1000):
           return False
   return True

def rezolvare(n, m, operatii):

   tablou = [0] * n
   for op in operatii:
       for i in range(op[0] - 1, op[1]):
           tablou[i] += op[2]
   return tablou

if __name__ == "__main__":

   n, m = map(int, input().split())
   operatii = []
   for _ in range(m):
       s, d, x = map(int, input().split())
       operatii.append((s, d, x))

   if not validare(n, m, operatii):
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       tablou = rezolvare(n, m, operatii)
       print(*tablou)

</syntaxhighlight>

Explicatie Rezolvare

Funcția validare_date_intrare(n, m, operatii) primește numărul de elemente din tablou n, numărul de operații m și o listă de m triplete operatii de forma (s, d, X) și verifică dacă toate aceste date de intrare sunt valide conform cerințelor problemei. Dacă datele de intrare sunt corecte, funcția returnează True. În caz contrar, returnează False.

Funcția rezolva_tablou(n, m, operatii) primește datele de intrare valide și realizează tabloul final prin aplicarea celor m operații, folosind o buclă for care parcurge lista de operații și modifică elementele corespunzătoare ale tabloului. Funcția returnează lista finală de n elemente.

Funcția afisare_rezultat(tablou) primește lista finală de n elemente și o afișează sub forma unei șiruri de numere separate printr-un spațiu, folosind funcția join pentru a uni elementele listei.

Funcția if __name__ == "__main__": reprezintă punctul de intrare în program și conține apelurile funcțiilor validare_date_intrare, rezolva_tablou și afisare_rezultat. Dacă datele de intrare sunt valide, se apelează funcțiile rezolva_tablou și afisare_rezultat, altfel se afișează mesajul "Datele nu corespund restricțiilor impuse.".