4177 - livada2

Sursa: 4177 - livada2

---

Cerinţa

Fiind un băiat aventurier, călărețul Jonathan obișnuia să umble prin pădurile magice ale împărăției tatălui său. În interiorul meleagurilor lui, împăratul avea o livadă specială, în cadrul căreia se aflau n meri magici, numerotați de la 1 la n, fiecare măr i conținând o cantitate cunoscută m[i] de fructe. Fiind speciali, cantitatea de fructe din acești meri putea fi modificată. Ca în orice poveste, împăratul avea un dușman, pe vrăjitorul Afida, care dorea să-i atace livada. Cunoscând acest fapt, Jonathan, fiul împăratului, dorește să protejeze livada tatălui său. Cei doi se confruntă în livadă, fiecare făcând modificări asupra merilor. Există în total q modificări, fiind de două tipuri:

1 x y p: cantitatea de fructe din merii cu indici cuprinși între x și y crește cu p, fiind o modificare făcută de Jonathan

2 x y p: cantitatea de fructe din merii cu indici cuprinși între x și y scade cu p, fiind o modificare făcută de vrăjitorul Afida

Mai mult: În cadrul livezii împăratului, există câțiva meri extra magici care influențează modificările pe care le fac cei doi. Dacă în cadrul unei modificări a lui Jonathan, după y există un măr extra magic t, astfel încât între y și t nu există alt măr extra magic, interogarea cuprinsă între x și y se va transforma în interogare între x și t. Dacă în cadrul unei modificări a lui Afida, înaintea lui x există un măr extra magic t, astfel încât între t și x nu există alt măr extra magic, interogarea cuprinsă între x și y se va transforma în interogare între t și y. Să se afișeze cantitatea de fructe din fiecare măr după cele q modificări.

Date de intrare

Pe prima linie a fișierului livada2.in se găsește numărul n. Pe următoarea linie se găsesc n numere întregi, separate printr-un spațiu, al i-lea număr reprezentând cantitatea de fructe din mărul corespunzător. Pe următoarea linie se găsesc n numere, 0 sau 1, separate printr-un spațiu, valorile 1 indicând faptul că mărul de pe poziția i este extra special. Pe a 4-a linie se află numărul q de modificări. Următoarele q linii vor conține interogările, fiind de forma: c x y p. Dacă c=1, modificarea este făcută de Jonathan. Dacă c=2, modificarea este făcută de vrăjitorul Afida.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." în fișierul livada2.out vor fi afișate n numere întregi separate prin câte un spațiu, reprezentând valorile din m, adică cantitatea de fructe a fiecărui măr, 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 ≤ 100.000
• 1 ≤ q ≤ 250.000
• 1 ≤ m[i] ≤ 1000, pentru 1 ≤ i ≤ n
• Pentru 40 de puncte, q ≤ 1000 și n ≤ 1000
• Pentru alte 20 de puncte, nu vor exista meri extra speciali

Exemplu 1

Intrare

livada2.in

10

17 18 2 21 14 6 13 14 8 10

1 1 0 0 0 0 1 0 0 0

7

2 4 7 3

1 8 9 16

2 8 8 25

2 4 4 8

1 2 8 1

2 8 9 21

1 5 6 19

Ieșire

Datele sunt introduse correct.

livada2.out

17 8 -8 11 31 23 -16 -15 3 10

Exemplu 2

Intrare

livada2.in

10

17 18 2 21 14 6 13 14 8 10

1 1 0 0 0 0 1 0 0 0

-1 2 3 -78 -23 2.34

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 4177 - livada2

def apply_query(n, m, is_extra, query):

   c, x, y, p = query
   x -= 1  # convertim la 0-indexing
   y -= 1
   t1, t2 = None, None
   for i in range(x, y + 1):
       if is_extra[i]:
           if i < y and not t1:
               t1 = i
           if i > x and not t2:
               t2 = i
   if c == 1:  # modificarea lui Jonathan
       for i in range(x, y + 1):
           if t1 and i > t1:
               break
           m[i] += p
   else:  # modificarea lui Afida
       for i in range(y, x - 1, -1):
           if t2 and i < t2:
               break
           m[i] -= p

def validate(n, m):

   for i in range(n):
       assert m[i] >= 0

def write_output(m):

   with open("livada2.out", "w") as file:
       file.write("Datele sunt introduse corect.\n")
       file.write(" ".join(map(str, m)))

def solve_problem(n, m, is_extra, q, queries):

   try:
       validate(n, m)
       for query in queries:
           apply_query(n, m, is_extra, query)
       write_output(m)
   except AssertionError:
       print("Datele nu corespund restricțiilor impuse.")

if __name__ == "__main__":

   n = int(input())
   m = list(map(int, input().split()))
   is_extra = list(map(int, input().split()))
   q = int(input())
   queries = []
   for i in range(q):
       query = list(map(int, input().split()))
       queries.append(query)
   solve_problem(n, m, is_extra, q, queries)

</syntaxhighlight>

Explicatie Rezolvare

apply_query(n, m, is_extra, query): Această funcție primește parametrii n, m, is_extra și query și aplică modificarea specificată de interogare (query) asupra listei m. Modificările sunt efectuate conform regulilor specificate în cerință. Funcția nu returnează nimic, deoarece modificările sunt aplicate direct asupra listei m.

validate(n, m): Această funcție primește parametrii n și m și verifică dacă valorile din lista m respectă restricțiile impuse. Dacă găsește o valoare negativă, ridică o excepție AssertionError. Dacă nu există excepții, se consideră că datele sunt valide.

write_output(m): Această funcție primește lista m și scrie rezultatul în fișierul "livada2.out". În fișier, se afișează mesajul "Datele sunt introduse corect." urmat de valorile din lista m separate prin spații.

solve_problem(n, m, is_extra, q, queries): Această funcție primește toți parametrii necesari pentru a rezolva problema. Ea se ocupă de apelarea celorlalte funcții în ordinea corectă. Mai întâi, verifică dacă datele sunt valide utilizând funcția validate. Apoi, aplică fiecare interogare din lista queries utilizând funcția apply_query. La final, scrie rezultatul în fișierul de ieșire utilizând funcția write_output.

Blocul if __name__ == "__main__": Acest bloc verifică dacă codul este executat direct (nu importat ca modul). În acest caz, se face citirea datelor de intrare utilizând funcția input() și se apelează funcția solve_problem cu parametrii corespunzători.