3453 - jungla - Revision history

Aurelia Raluca at 22:28, 22 March 2024

2024-03-22T22:28:31Z

← Older revision	Revision as of 22:28, 22 March 2024
Line 1:	Line 1:
		= Cerința =
		În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut <code>N</code> numere, <code>v[1], v[2], ..., v[N]</code>, unde <code>V[i]</code> reprezintă înălțimea copacului <code>i</code>. Apoi i-au venit în minte două întrebări.

		Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine <code>i</code> au înălțimile mai mici ca acesta.

		A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate <code>(1,1)</code> , iar cel din dreapta sus de coordonate <code>(N,H)</code>, unde <code>N</code> este numărul de copaci, iar <code>H</code> este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine <code>i</code> ocupă primele <code>v[i]</code> unități de pe coloana <code>i</code>, de jos in sus (<code>v[i]</code> reprezintă înălțimea copacului <code>i</code>).

		= Date de intrare =
		Programul citește de la tastatură un număr <code>p</code>, care poate avea valorile <code>1</code> sau <code>2</code>, în funcție de cerința problemei.

		Pentru <code>p = 1</code>, următorul rând conține numerele <code>N q</code>. Următorul rând conține <code>n</code> valori, a <code>i</code> -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține <code>q</code> numere; pentru fiecare număr <code>i</code> se cere numarul de copaci plantați înaintea copacului cu numărul de ordine <code>i</code> cu înălțimi mai mici ca acesta.

		Pentru <code>p = 2</code>, următorul rând va conține doar numărul <code>N</code>, iar ultimul rând va conține <code>N</code> valori reprezentând înălțimile copacilor.

		= Date de ieșire =
		Pentru <code>p = 1</code> programul va afișa <code>q</code> linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele <code>q</code> numere date.

		Pentru <code>p = 2</code> programul fa afișa singur numar, reprezentând raspunsul pentru cerinta <code>2</code> , adică dreptunghiul liber de arie maximă.

		= Restricții și precizări =

		* Pentru cerința 1, <code>n ≤ 1000</code>, iar pentru cerința 2, <code>n ≤ 100.000</code>
		* înâlțimile copacilor vor fi numere naturale nenule mi mici decât <code>15.000</code>
		* <code>1 ≤ q ≤ 2*n</code>
		* Pentru 25 de puncte cerința este 1.

		= Exemplul 1: =
		Intrare
		1
		7 3
		4 2 6 8 3 4 2
		2 4 6
		Ieșire
		0
		3
		2

		= Exemplul 2: =
		Intrare
		2
		11
		4 6 5 4 6 8 8 10 6 3 2
		Ieșire
		20

		=== Explicație ===
		Pentru exemplul 1: <code>p=1</code> deci se rezolvă doar cerința 1. Inainte de copacul cu numărul de ordine <code>2</code> nu există copaci cu înalțimi mai mici, înainte de copacul cu numărul de ordine <code>4</code> există <code>3</code> copaci mai mici, iar înainte de copacul <code>6</code> există <code>2</code> copaci mai mici.

		Pentru exemplul 2, sera ar arăta astfel:
		o o o o o o o 1 o o
		o o o o o o o 1 o o
		o o o o o 1 1 1 o o
		o o o o o 1 1 1 o o
		o 1 o o 1 1 1 1 o o
		o 1 1 o 1 1 1 1 o o
		1 1 1 1 1 1 1 1 o o
		1 1 1 1 1 1 1 1 1 o
		1 1 1 1 1 1 1 1 1 1
		1 1 1 1 1 1 1 1 1 1
		Unde <code>o</code> reprezinta zona liberă, iar <code>1</code> reprezintă o zona ocupată de copac. Suprafața dreptunghiulară maximă este de <code>20</code> de unități.

		== Exemplul 3: ==
		Intrare
		2
		123123213
		Ieșire
		Datele nu corespund restrictiilor impuse

		== Rezolvare ==
		<syntaxhighlight lang="python3" line="1">
		def verifica_restricții(cer, n, q=None, v=None):
		if v and any(h <= 0 or h >= 15000 for h in v):
		print("Datele nu corespund restrictiilor impuse")
		return False

		if cer == 1:
		if not (1 <= n <= 1000) or not (1 <= q <= 2*n):
		print("Datele nu corespund restrictiilor impuse")
		return False
		elif cer == 2:
		if not (1 <= n <= 100000):
		print("Datele nu corespund restrictiilor impuse")
		return False
		else:
		print("Cerința specificată este invalidă.")
		return False
		return True

		def main():
		cer = int(input())
		if cer == 1:
		n, q = map(int, input().split())
		if not verifica_restricții(cer, n, q):
		return
		v = [0] + list(map(int, input().split()))
		queries = list(map(int, input().split()))
		for j in queries:
		copaci = 0
		for i in range(1, j):
		if v[i] < v[j]:
		copaci += 1
		print(copaci)
		elif cer == 2:
		n = int(input())
		if not verifica_restricții(cer, n):
		return
		v = [0] + list(map(int, input().split()))
		max_height = max(v)
		for i in range(1, n + 1):
		v[i] = max_height - v[i]
		st = [0] * (n + 1)
		dr = [0] * (n + 1)
		stack = []
		for i in range(1, n + 1):
		while stack and v[stack[-1]] >= v[i]:
		stack.pop()
		st[i] = stack[-1] if stack else 0
		stack.append(i)
		stack = []
		for i in range(n, 0, -1):
		while stack and v[stack[-1]] >= v[i]:
		stack.pop()
		dr[i] = stack[-1] if stack else n + 1
		stack.append(i)
		arie_max = 0
		for i in range(1, n + 1):
		arie_max = max(arie_max, v[i] * (dr[i] - st[i] - 1))
		print(arie_max)

		if __name__ == "__main__":
		main()

		</syntaxhighlight>

Aurelia Raluca: Ștergerea conținutului paginii

2024-02-24T13:18:28Z

Ștergerea conținutului paginii

← Older revision		Revision as of 13:18, 24 February 2024
Line 1:		Line 1:
	~~== Cerinta ==~~
	În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.

	~~Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.~~

	A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).

	~~== Date de intrare ==~~
	~~Programul citește de la tastatură un număr p, care poate avea valorile 1 sau 2, în funcție de cerința problemei.~~

	Pentru p = 1, următorul rând conține numerele N q. Următorul rând conține n valori, a i -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține q numere; pentru fiecare număr i se cere numarul de copaci plantați înaintea copacului cu numărul de ordine i cu înălțimi mai mici ca acesta.

	~~Pentru p = 2, următorul rând va conține doar numărul N, iar ultimul rând va conține N valori reprezentând înălțimile copacilor.~~

	~~== Date de iesire ==~~
	~~Pentru p = 1 programul va afișa q linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele q numere date.~~

	~~Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.~~

	~~== Restricti1 si precizari ==~~
	*Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000
	*înâlțimile copacilor vor fi numere naturale nenule mi mai mici decât 15.000
	1 ≤ q ≤ 2n
	*Pentru 25 de puncte cerința este 1.

	~~== Exemplu 1 ==~~

	~~;intrare~~
	:1
	~~:7 3~~
	~~:4 2 6 8 3 4 2~~
	~~:2 4 6~~

	~~;iesire~~
	~~;Datele introduse corespund restrictiilor impuse~~
	:0
	:3
	:2


	~~== Exemplul 2 ==~~

	~~;intrare~~

	:3

	~~:12~~

	~~:7 8 9 9 11 9 6 7 2 1 3~~

	~~;iesire~~

	~~;Datele de intrare nu corespund restrictiilor impuse~~

	~~== Rezolvare ==~~
	~~<syntaxhighlight lang="python3"line="1">~~
	~~def copaci_cu_inaltimi_mici(v):~~
	~~n = len(v)~~
	~~cnt_copaci_mici = [0] * n~~

	~~for i in range(1, n):~~
	~~for j in range(i):~~
	~~if v[i] > v[j]:~~
	~~cnt_copaci_mici[i] += 1~~

	~~return cnt_copaci_mici~~


	~~def suprafata_maxima_liber(v):~~
	~~n = len(v)~~
	~~stiva = []~~
	~~max_suprafata = 0~~

	~~for i in range(n):~~
	~~while stiva and v[i] <= v[stiva[-1]]:~~
	~~h = v[stiva.pop()]~~
	~~w = i if not stiva else i - stiva[-1] - 1~~
	~~max_suprafata = max(max_suprafata, h * w)~~
	~~stiva.append(i)~~

	~~while stiva:~~
	~~h = v[stiva.pop()]~~
	~~w = n if not stiva else n - stiva[-1] - 1~~
	~~max_suprafata = max(max_suprafata, h * w)~~

	~~return max_suprafata~~

	~~</syntaxhighlight>~~

Aurelia Raluca: /* Exemplul 2 */

2023-12-30T09:38:23Z

Exemplul 2

← Older revision		Revision as of 09:38, 30 December 2023
Line 42:		Line 42:

	;intrare		;intrare

	:3		:3

	:12		:12

	:7 8 9 9 11 9 6 7 2 1 3		:7 8 9 9 11 9 6 7 2 1 3

	;iesire		;iesire
	;Datele nu corespund restrictiilor impuse
			;Datele de intrare nu corespund restrictiilor impuse

	== Rezolvare ==		== Rezolvare ==

Aurelia Raluca: /* Rezolvare */

2023-12-30T09:37:03Z

Rezolvare

← Older revision		Revision as of 09:37, 30 December 2023
Line 62:		Line 62:
	return cnt_copaci_mici		return cnt_copaci_mici

	~~# Exemplu de folosire~~
	~~v = [3, 1, 4, 2, 5]~~
	~~rezultat = copaci_cu_inaltimi_mici(v)~~
	~~print(rezultat)~~

	def suprafata_maxima_liber(v):		def suprafata_maxima_liber(v):
Line 86:		Line 82:
	return max_suprafata		return max_suprafata

	~~# Exemplu de folosire~~
	~~v = [3, 1, 4, 2, 5]~~
	~~rezultat = suprafata_maxima_liber(v)~~
	~~print(rezultat)~~
	</syntaxhighlight>		</syntaxhighlight>

Aurelia Raluca: /* Restricti si precizari */

2023-12-30T09:36:01Z

Restricti si precizari

← Older revision		Revision as of 09:36, 30 December 2023
Line 18:		Line 18:
	Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.		Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.

	== ~~Restricti~~ si precizari ==		== Restricti1 si precizari ==
	*Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000		*Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000
	*înâlțimile copacilor vor fi numere naturale nenule mi mici decât 15.000		*înâlțimile copacilor vor fi numere naturale nenule mi mai mici decât 15.000
	1 ≤ q ≤ 2n		1 ≤ q ≤ 2n
	*Pentru 25 de puncte cerința este 1.		*Pentru 25 de puncte cerința este 1.

Aurelia Raluca: /* Cerinta */

2023-12-30T09:26:41Z

Cerinta

← Older revision		Revision as of 09:26, 30 December 2023
Line 2:		Line 2:
	În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.		În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.

	Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).		Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.

			A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).

	== Date de intrare ==		== Date de intrare ==

Aurelia Raluca at 13:35, 13 December 2023

2023-12-13T13:35:10Z

← Older revision		Revision as of 13:35, 13 December 2023
Line 48:		Line 48:

	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang=~~'python'~~line>		<syntaxhighlight lang="python3"line="1">
	def copaci_cu_inaltimi_mici(v):		def copaci_cu_inaltimi_mici(v):
	n = len(v)		n = len(v)
Line 88:		Line 88:
	rezultat = suprafata_maxima_liber(v)		rezultat = suprafata_maxima_liber(v)
	print(rezultat)		print(rezultat)
	</~~sybtaxhighlight~~>		</syntaxhighlight>

Aurelia Raluca: Pagină nouă: == Cerinta == În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit î...

2023-12-13T09:08:21Z

Pagină nouă: == Cerinta == În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit î...

New page

== Cerinta ==
În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.

Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).

== Date de intrare ==
Programul citește de la tastatură un număr p, care poate avea valorile 1 sau 2, în funcție de cerința problemei.

Pentru p = 1, următorul rând conține numerele N q. Următorul rând conține n valori, a i -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține q numere; pentru fiecare număr i se cere numarul de copaci plantați înaintea copacului cu numărul de ordine i cu înălțimi mai mici ca acesta.

Pentru p = 2, următorul rând va conține doar numărul N, iar ultimul rând va conține N valori reprezentând înălțimile copacilor.

== Date de iesire ==
Pentru p = 1 programul va afișa q linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele q numere date.

Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.

== Restricti si precizari ==
*Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000
*înâlțimile copacilor vor fi numere naturale nenule mi mici decât 15.000
*1 ≤ q ≤ 2*n
*Pentru 25 de puncte cerința este 1.

== Exemplu 1 ==

;intrare
:1
:7 3
:4 2 6 8 3 4 2
:2 4 6

;iesire
;Datele introduse corespund restrictiilor impuse
:0
:3
:2

== Exemplul 2 ==

;intrare
:3
:12
:7 8 9 9 11 9 6 7 2 1 3

;iesire
;Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang='python'line>
def copaci_cu_inaltimi_mici(v):
n = len(v)
cnt_copaci_mici = [0] * n

for i in range(1, n):
for j in range(i):
if v[i] > v[j]:
cnt_copaci_mici[i] += 1

return cnt_copaci_mici

# Exemplu de folosire
v = [3, 1, 4, 2, 5]
rezultat = copaci_cu_inaltimi_mici(v)
print(rezultat)

def suprafata_maxima_liber(v):
n = len(v)
stiva = []
max_suprafata = 0

for i in range(n):
while stiva and v[i] <= v[stiva[-1]]:
h = v[stiva.pop()]
w = i if not stiva else i - stiva[-1] - 1
max_suprafata = max(max_suprafata, h * w)
stiva.append(i)

while stiva:
h = v[stiva.pop()]
w = n if not stiva else n - stiva[-1] - 1
max_suprafata = max(max_suprafata, h * w)

return max_suprafata

# Exemplu de folosire
v = [3, 1, 4, 2, 5]
rezultat = suprafata_maxima_liber(v)
print(rezultat)
</sybtaxhighlight>