4177 - livada2 - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-14T22:29:26Z

Date de ieșire

← Older revision		Revision as of 22:29, 14 May 2023
Line 18:		Line 18:

	== Date de ieșire ==		== Date de ieșire ==
	~~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 '''~~ 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."'''.		'''"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 ==		== Restricţii şi precizări ==

Monica Dragos at 22:28, 14 May 2023

2023-05-14T22:28:30Z

← Older revision		Revision as of 22:28, 14 May 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/4177/livada2 4177 - livada2]		Sursa: [https://www.pbinfo.ro/probleme/4177/livada2 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:		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:

Line 8:		Line 11:

	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.		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.		Să se afișeze cantitatea de fructe din fiecare măr după cele q modificări.

Flaviu at 21:41, 14 May 2023

2023-05-14T21:41:28Z

← Older revision		Revision as of 21:41, 14 May 2023
Line 42:		Line 42:
	: 1 5 6 19		: 1 5 6 19
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: livada2.out		: livada2.out
	~~: Datele sunt introduse correct.~~
	: 17 8 -8 11 31 23 -16 -15 3 10		: 17 8 -8 11 31 23 -16 -15 3 10

Line 54:		Line 54:
	: -1 2 3 -78 -23 2.34		: -1 2 3 -78 -23 2.34
	; Ieșire		; Ieșire
	~~: livada2.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 62:		Line 61:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 4177 - livada2		# 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):		def apply_query(n, m, is_extra, query):
Line 80:		Line 67:
	y -= 1		y -= 1
	t1, t2 = None, None		t1, t2 = None, None
	for i in range(x, y+1):		for i in range(x, y + 1):
	if is_extra[i]:		if is_extra[i]:
	if i < y and not t1:		if i < y and not t1:
Line 87:		Line 74:
	t2 = i		t2 = i
	if c == 1: # modificarea lui Jonathan		if c == 1: # modificarea lui Jonathan
	for i in range(x, y+1):		for i in range(x, y + 1):
	if t1 and i > t1:		if t1 and i > t1:
	break		break
	m[i] += p		m[i] += p
	else: # modificarea lui Afida		else: # modificarea lui Afida
	for i in range(y, x-1, -1):		for i in range(y, x - 1, -1):
	if t2 and i < t2:		if t2 and i < t2:
	break		break
Line 103:		Line 90:


	~~if __name__ == '__main__'~~:		def write_output(m):
	n, m, is_extra, q, queries ~~= read_input(~~)		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:		try:
	validate(n, m)		validate(n, m)
	for query in queries:		for query in queries:
	apply_query(n, m, is_extra, query)		apply_query(n, m, is_extra, query)
	~~print~~(~~"Datele sunt introduse corect.")~~		write_output(m)
	print(*m)
	except AssertionError:		except AssertionError:
	print("Datele nu corespund restricțiilor impuse.")		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>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Se definește funcția read_input~~() ~~care citește input-ul format din următoarele variabile~~:		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.
	n ~~- numărul de elemente din lista m.~~
	m ~~- o listă de n elemente~~, ~~reprezentând valorile inițiale ale elementelor.~~		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.
	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~~.		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.

	~~Se definește funcția validate~~() ~~care~~ verifică ~~că toate elementele~~ din lista ~~m sunt pozitive~~.		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.

	~~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()~~.		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.

Flaviu at 08:03, 3 May 2023

2023-05-03T08:03:34Z

← Older revision		Revision as of 08:03, 3 May 2023
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 ==

Flaviu at 14:49, 28 April 2023

2023-04-28T14:49:31Z

← Older revision		Revision as of 14:49, 28 April 2023
Line 17:		Line 17:

	== Date de ieșire ==		== Date de ieșire ==
	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~~.		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 '''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 ==		== Restricţii şi precizări ==
Line 39:		Line 41:
	: 1 5 6 19		: 1 5 6 19
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 17 8 -8 11 31 23 -16 -15 3 10		: 17 8 -8 11 31 23 -16 -15 3 10

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



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru a rezolva această problemă~~, ~~vom crea~~ o listă ~~cu cantitatea~~ de ~~fructe din fiecare măr și~~ o ~~altă listă~~ care ~~va indica~~ dacă un ~~măr este extra magic~~ sau nu. ~~Vom itera prin~~ fiecare ~~modificare~~ și ~~vom actualiza cantitatea~~ de ~~fructe~~ din ~~mările afectate~~ de ~~aceasta~~. ~~În timpul actualizării, vom verifica dacă modificarea este înainte sau după un măr extra magic și vom actualiza~~ intervalul ~~corespunzător~~. ~~La final, vom afișa lista actualizată cu cantitatea de fructe~~.		Se definește funcția read_input() care citește input-ul format din următoarele variabile:
	Funcția read_input() citește ~~datele de intrare~~ și le ~~returnează~~ sub formă de ~~tuple~~. ~~Funcția~~ apply_query() ~~primește~~ o ~~modificare și actualizează cantitatea~~ de ~~fructe~~ din ~~merii afectați~~ de ~~aceasta~~. ~~Funcția~~ validate() verifică că toate ~~cantitățile de fructe~~ sunt pozitive. ~~În funcția main~~, ~~citim datele de intrare~~, ~~aplicăm modificările~~ și ~~validăm soluția~~.		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().

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4177/livada2 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ă....

2023-04-18T07:00:29Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4177/livada2 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ă....

New page

Sursa: [https://www.pbinfo.ro/probleme/4177/livada2 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 n numere întregi separate prin câte un spațiu, reprezentând valorile din m, adică cantitatea de fructe a fiecărui măr.

== 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 ==
; Intrare
: 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
: 17 8 -8 11 31 23 -16 -15 3 10

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 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()
for query in queries:
apply_query(n, m, is_extra, query)
validate(n, m)
print(*m)

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, vom crea o listă cu cantitatea de fructe din fiecare măr și o altă listă care va indica dacă un măr este extra magic sau nu. Vom itera prin fiecare modificare și vom actualiza cantitatea de fructe din mările afectate de aceasta. În timpul actualizării, vom verifica dacă modificarea este înainte sau după un măr extra magic și vom actualiza intervalul corespunzător. La final, vom afișa lista actualizată cu cantitatea de fructe.
Funcția read_input() citește datele de intrare și le returnează sub formă de tuple. Funcția apply_query() primește o modificare și actualizează cantitatea de fructe din merii afectați de aceasta. Funcția validate() verifică că toate cantitățile de fructe sunt pozitive. În funcția main, citim datele de intrare, aplicăm modificările și validăm soluția.