4177 - livada2: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 19: Line 19:
n fișierul livada2.out vor fi afișate:
n fișierul livada2.out vor fi afișate:
Dacă datele sunt introduse corect, pe ecran se va afișa:  
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."'''.
'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' 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 ==
== Restricţii şi precizări ==
Line 27: Line 27:
* Pentru 40 de puncte, q ≤ 1000 și n ≤ 1000
* Pentru 40 de puncte, q ≤ 1000 și n ≤ 1000
* Pentru alte 20 de puncte, nu vor exista meri extra speciali
* Pentru alte 20 de puncte, nu vor exista meri extra speciali
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: livada2.in
: 10
: 10
: 17 18 2 21 14 6 13 14 8 10  
: 17 18 2 21 14 6 13 14 8 10  
Line 41: Line 42:
: 1 5 6 19
: 1 5 6 19
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: livada2.out
: Datele sunt introduse correct.
: Datele sunt introduse correct.
: 17 8 -8 11 31 23 -16 -15 3 10
: 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
: livada2.out
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  

Revision as of 08:03, 3 May 2023

Sursa: 4177 - livada2


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.

Cerinţa

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

n fișierul livada2.out vor fi afișate: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou 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
livada2.out
Datele sunt introduse correct.
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
livada2.out
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 4177 - livada2

def read_input():

   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)
   return n, m, is_extra, q, queries


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


if __name__ == '__main__':

   n, m, is_extra, q, queries = read_input()
   try:
       validate(n, m)
       for query in queries:
           apply_query(n, m, is_extra, query)
       print("Datele sunt introduse corect.")
       print(*m)
   except AssertionError:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

Se definește funcția read_input() care citește input-ul format din următoarele variabile: n - numărul de elemente din lista m. m - o listă de n elemente, reprezentând valorile inițiale ale elementelor. is_extra - o listă de n elemente, reprezentând o serie de indicatori (0 sau 1) care specifică dacă un element suplimentar trebuie adăugat sau nu la poziția corespunzătoare din lista m. q - numărul de operații care trebuie aplicate pe lista m. queries - o listă de q elemente, fiecare element fiind reprezentat de o altă listă formată din patru elemente: c, x, y și p, unde: c - tipul de operație (1 sau 2). x - poziția din lista m de unde începe aplicarea operației. y - poziția din lista m unde se termină aplicarea operației. p - valoarea cu care se modifică elementele din intervalul m[x..y]. Funcția read_input() citește toate aceste variabile și le întoarce sub formă de tuplu.

Se definește funcția apply_query() care aplică o singură operație din lista de operații queries pe lista m. În funcție de tipul operației (c), aceasta adaugă sau scade valoarea p la toate elementele din intervalul m[x..y] care respectă anumite condiții specificate de variabilele is_extra, t1 și t2.

Se definește funcția validate() care verifică că toate elementele din lista m sunt pozitive.

Se citește input-ul, se aplică toate operațiile din lista queries pe lista m, se validează lista m și, dacă toate elementele din aceasta sunt pozitive, se afișează lista m cu ajutorul funcției print().