0839 - Vraja2 - Revision history

Catalin Moje at 20:33, 14 May 2023

2023-05-14T20:33:34Z

← Older revision		Revision as of 20:33, 14 May 2023
Line 90:		Line 90:
	Codul este structurat astfel:		Codul este structurat astfel:

	# validare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și verifică dacă datele de intrare respectă restricțiile problemei. În caz contrar, returnează False.		#1 validare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și verifică dacă datele de intrare respectă restricțiile problemei. În caz contrar, returnează False.

	# rezolvare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și calculează numărul minim de vrajitori necesari pentru a proteja toți copacii. În prima buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu primul. În a doua buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu ultimul. Rezultatul final este minimul dintre cele două valori. Dacă nu este posibil să se protejeze toți copacii, funcția returnează un mesaj de eroare.		#2 rezolvare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și calculează numărul minim de vrajitori necesari pentru a proteja toți copacii. În prima buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu primul. În a doua buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu ultimul. Rezultatul final este minimul dintre cele două valori. Dacă nu este posibil să se protejeze toți copacii, funcția returnează un mesaj de eroare.

	# main(): funcția principală care primește datele de intrare și afișează rezultatul. În cazul în care datele de intrare nu sunt valide, afișează un mesaj de eroare.		#3 main(): funcția principală care primește datele de intrare și afișează rezultatul. În cazul în care datele de intrare nu sunt valide, afișează un mesaj de eroare.

	Datele de intrare sunt citite prin intermediul funcției input() și sunt stocate într-o listă numită copaci. Pentru a calcula numărul minim de vrajitori necesari, se parcurg toți copacii și se verifică dacă fiecare copac este protejat de vrajitorii anteriori. Dacă nu este protejat, se adaugă un nou vrajitor și se protejează copacul curent.		Datele de intrare sunt citite prin intermediul funcției input() și sunt stocate într-o listă numită copaci. Pentru a calcula numărul minim de vrajitori necesari, se parcurg toți copacii și se verifică dacă fiecare copac este protejat de vrajitorii anteriori. Dacă nu este protejat, se adaugă un nou vrajitor și se protejează copacul curent.

	Rezultatul final este afișat prin intermediul funcției print(). Dacă nu este posibil să se protejeze toți copacii, se afișează un mesaj de eroare.		Rezultatul final este afișat prin intermediul funcției print(). Dacă nu este posibil să se protejeze toți copacii, se afișează un mesaj de eroare.

Catalin Moje at 20:33, 14 May 2023

2023-05-14T20:33:01Z

← Older revision		Revision as of 20:33, 14 May 2023
Line 13:		Line 13:
	==Restricții și precizări==		==Restricții și precizări==

	1 ≤ n ≤ 1000		*1 ≤ n ≤ 1000
	înălțimile arborilor sunt numere naturale nenule mai mici decât 1.000.000		*înălțimile arborilor sunt numere naturale nenule mai mici decât 1.000.000
	secvența aleasă de vrăjitor la un moment dat nu poate conține copaci de înălțime zero		*secvența aleasă de vrăjitor la un moment dat nu poate conține copaci de înălțime zero

	==Exemplu ==		==Exemplu ==
	===Exemplu 1===		===Exemplu 1===
	~~<syntaxhighlight lang="python">~~		:Intrare:
	Introduceti primul numar: 3		;Introduceti primul numar: 3
	Introduceti al doilea numar: 0		;Introduceti al doilea numar: 0
	Datele de intrare corespund restrictiilor		:Iesire:
	Numarul de moduri de a ajunge la scorul 3-0 este 1		;Datele de intrare corespund restrictiilor
	~~</syntaxhighlight>~~		;Numarul de moduri de a ajunge la scorul 3-0 este 1


	===Exemplu 2===		===Exemplu 2===
	~~<syntaxhighlight lang="python">~~		:Intrare:
	Introduceti numarul n: 0		;Introduceti numarul n: 0
	Datele de intrare nu corespund cerintei		:Iesire:
	~~</syntaxhighlight>~~		;Datele de intrare nu corespund cerintei



	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python" line="1">

	def calc_nr_vraj(copaci, idx):		def calc_nr_vraj(copaci, idx):
Line 88:		Line 90:
	Codul este structurat astfel:		Codul este structurat astfel:

	validare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și verifică dacă datele de intrare respectă restricțiile problemei. În caz contrar, returnează False.		# validare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și verifică dacă datele de intrare respectă restricțiile problemei. În caz contrar, returnează False.

	rezolvare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și calculează numărul minim de vrajitori necesari pentru a proteja toți copacii. În prima buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu primul. În a doua buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu ultimul. Rezultatul final este minimul dintre cele două valori. Dacă nu este posibil să se protejeze toți copacii, funcția returnează un mesaj de eroare.		# rezolvare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și calculează numărul minim de vrajitori necesari pentru a proteja toți copacii. În prima buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu primul. În a doua buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu ultimul. Rezultatul final este minimul dintre cele două valori. Dacă nu este posibil să se protejeze toți copacii, funcția returnează un mesaj de eroare.

	main(): funcția principală care primește datele de intrare și afișează rezultatul. În cazul în care datele de intrare nu sunt valide, afișează un mesaj de eroare.		# main(): funcția principală care primește datele de intrare și afișează rezultatul. În cazul în care datele de intrare nu sunt valide, afișează un mesaj de eroare.

	Datele de intrare sunt citite prin intermediul funcției input() și sunt stocate într-o listă numită copaci. Pentru a calcula numărul minim de vrajitori necesari, se parcurg toți copacii și se verifică dacă fiecare copac este protejat de vrajitorii anteriori. Dacă nu este protejat, se adaugă un nou vrajitor și se protejează copacul curent.		Datele de intrare sunt citite prin intermediul funcției input() și sunt stocate într-o listă numită copaci. Pentru a calcula numărul minim de vrajitori necesari, se parcurg toți copacii și se verifică dacă fiecare copac este protejat de vrajitorii anteriori. Dacă nu este protejat, se adaugă un nou vrajitor și se protejează copacul curent.

	Rezultatul final este afișat prin intermediul funcției print(). Dacă nu este posibil să se protejeze toți copacii, se afișează un mesaj de eroare.		Rezultatul final este afișat prin intermediul funcției print(). Dacă nu este posibil să se protejeze toți copacii, se afișează un mesaj de eroare.

Catalin Moje: Pagină nouă: ==Cerința== De-a lungul bulevardului sunt n copaci, numerotați de la 1 la n, pentru fiecare cunoscându-se înălțimea, exprimată în centimetri. Primarul dorește să taie copacii și apelează la un vrăjitor care va proceda astfel: alege o secvență cât mai lungă de copaci învecinați și aplică o vrajă prin care toți înălțimea tuturor copacilor din secvență scade cu o aceeași valoare, strict pozitivă. Să se determine care este numărul minim de vrăji...

2023-04-29T14:54:53Z

Pagină nouă: ==Cerința== De-a lungul bulevardului sunt n copaci, numerotați de la 1 la n, pentru fiecare cunoscându-se înălțimea, exprimată în centimetri. Primarul dorește să taie copacii și apelează la un vrăjitor care va proceda astfel: alege o secvență cât mai lungă de copaci învecinați și aplică o vrajă prin care toți înălțimea tuturor copacilor din secvență scade cu o aceeași valoare, strict pozitivă. Să se determine care este numărul minim de vrăji...

New page

==Cerința==
De-a lungul bulevardului sunt n copaci, numerotați de la 1 la n, pentru fiecare cunoscându-se înălțimea, exprimată în centimetri. Primarul dorește să taie copacii și apelează la un vrăjitor care va proceda astfel: alege o secvență cât mai lungă de copaci învecinați și aplică o vrajă prin care toți înălțimea tuturor copacilor din secvență scade cu o aceeași valoare, strict pozitivă.

Să se determine care este numărul minim de vrăji care trebuie aplicate astfel încât toți copacii să aibă înălțime zero.

==Date de intrare==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând înălțimile copacilor.

=Date de ieșire==
Dacă datele de intrare corespund restrictiilor impuse se va afișa mesajul "Datele de intrare corespund restricțiilor" și pe un rând nou se afișează ceea ce se cere. Altfel, dacă datele de intrare nu corespund cerinței se va afișa mesajul: "Datele de intrare nu corespund cerinței".

==Restricții și precizări==

1 ≤ n ≤ 1000
înălțimile arborilor sunt numere naturale nenule mai mici decât 1.000.000
secvența aleasă de vrăjitor la un moment dat nu poate conține copaci de înălțime zero

==Exemplu ==
===Exemplu 1===
<syntaxhighlight lang="python">
Introduceti primul numar: 3
Introduceti al doilea numar: 0
Datele de intrare corespund restrictiilor
Numarul de moduri de a ajunge la scorul 3-0 este 1
</syntaxhighlight>

===Exemplu 2===
<syntaxhighlight lang="python">
Introduceti numarul n: 0
Datele de intrare nu corespund cerintei
</syntaxhighlight>

==Rezolvare==
<syntaxhighlight lang="python">

def calc_nr_vraj(copaci, idx):
# Verificam in stanga pana la primul copac cu inaltime mai mare
for i in range(idx-1, -1, -1):
if copaci[i] > copaci[idx]:
return idx - i
# Daca nu am gasit copac mai mare in stanga, cautam in dreapta
for i in range(idx+1, len(copaci)):
if copaci[i] > copaci[idx]:
return i - idx
# Daca nu am gasit copac mai mare nici in stanga nici in dreapta
return 0

def rezolvare(n, copaci):
nr_vraj = 0
for i in range(n):
nr_vraj += calc_nr_vraj(copaci, i)
return nr_vraj

def validare(n, copaci):
if not (2 <= n <= 10**5):
return False
for h in copaci:
if not (1 <= h <= 10**9):
return False
return True

def main():
n = int(input("Introduceti numarul n: "))
copaci = []
for i in range(n):
inaltime = int(input(f"Introduceti inaltimea copacului {i+1}: "))
copaci.append(inaltime)

if validare(n, copaci):
print("Datele de intrare corespund restrictiilor")
nr_vraj = rezolvare(n, copaci)
print(f"Numarul minim de vraji necesare este: {nr_vraj}")
else:
print("Datele de intrare nu corespund cerintei")

if __name__ == '__main__':
main()

</syntaxhighlight>

==Explicații ==
Codul este structurat astfel:

validare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și verifică dacă datele de intrare respectă restricțiile problemei. În caz contrar, returnează False.

rezolvare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și calculează numărul minim de vrajitori necesari pentru a proteja toți copacii. În prima buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu primul. În a doua buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu ultimul. Rezultatul final este minimul dintre cele două valori. Dacă nu este posibil să se protejeze toți copacii, funcția returnează un mesaj de eroare.

main(): funcția principală care primește datele de intrare și afișează rezultatul. În cazul în care datele de intrare nu sunt valide, afișează un mesaj de eroare.

Datele de intrare sunt citite prin intermediul funcției input() și sunt stocate într-o listă numită copaci. Pentru a calcula numărul minim de vrajitori necesari, se parcurg toți copacii și se verifică dacă fiecare copac este protejat de vrajitorii anteriori. Dacă nu este protejat, se adaugă un nou vrajitor și se protejează copacul curent.

Rezultatul final este afișat prin intermediul funcției print(). Dacă nu este posibil să se protejeze toți copacii, se afișează un mesaj de eroare.