1512 - Mars

From Bitnami MediaWiki
Revision as of 18:48, 27 April 2023 by Flaviu (talk | contribs)

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 numărul c, 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

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

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  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.