1461 - Meteoriti - Revision history

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

2023-05-04T20:48:52Z

Date de ieșire

← Older revision		Revision as of 20:48, 4 May 2023
Line 9:		Line 9:
	==Date de ieșire==		==Date de ieșire==
	În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.		În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.
	În consolă se va afișa un mesaj de validare a datelor ("Input valid" ~~sau~~ "Input invalid" ~~după caz)~~.		În consolă se va afișa un mesaj de validare a datelor "Input valid" în acest caz. În caz contrar, pe consolă se va afișa mesajul "Input invalid".

	==Restricții și precizări==		==Restricții și precizări==
	* 4 ≤ N, M ≤ 2.000		* 4 ≤ N, M ≤ 2.000

Cata at 06:52, 3 May 2023

2023-05-03T06:52:16Z

← Older revision		Revision as of 06:52, 3 May 2023
Line 9:		Line 9:
	==Date de ieșire==		==Date de ieșire==
	În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.		În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.
	În consolă se va afișa un mesaj de validare a datelor.		În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau "Input invalid" după caz).
	==Restricții și precizări==		==Restricții și precizări==
	* 4 ≤ N, M ≤ 2.000		* 4 ≤ N, M ≤ 2.000
Line 51:		Line 51:
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
	nmax = 210*3		nmax = 210*3
			# liste care stochează schimbările de linie și coloană pentru a putea naviga în matricea 2D a meteoritelor din program
	dl = [-1, 0, 1, 0]		dl = [-1, 0, 1, 0]
	dc = [0, 1, 0, -1]		dc = [0, 1, 0, -1]
Line 130:		Line 131:
	r1, r2 = r1 - 1, r2 - 1		r1, r2 = r1 - 1, r2 - 1
	c1, c2 = c1 - 1, c2 - 1		c1, c2 = c1 - 1, c2 - 1
	~~# Marks on matrix~~
	a[r1][c1] += x		a[r1][c1] += x
	a[r1][c2 + 1] -= x		a[r1][c2 + 1] -= x
Line 141:		Line 141:

	==Explicație cod==		==Explicație cod==
	Acest ~~cod este o soluție a unui problema~~ de ~~tip algoritmica, numită~~ "~~Meteoriți~~", ~~care implică procesarea unei matrici mari~~ și ~~determinarea unor proprietăți ale acesteia. Scopul problemei este de a găsi aria celui~~ mai mare ~~grup~~ de ~~celule în care valorile din matrice sunt egale~~ și~~, de asemenea,~~ de a ~~găsi numărul de celule din matrice care au valoarea 0~~. ~~Intrarea constă în~~ dimensiunile matricei, numărul de ~~meteorite care lovesc matricea~~ și ~~informații despre locul~~ și ~~efectul fiecărui meteorit~~. ~~Matricea este actualizată~~ în ~~funcție~~ de ~~locurile~~ în ~~care loviturile~~ de ~~meteorit au avut loc~~. ~~Codul~~ utilizează o ~~abordare~~ de ~~căutare~~ în ~~lățime~~ pentru a determina ~~aria celor~~ mai ~~mari~~ zone în ~~care valorile~~ sunt ~~egale~~ și ~~urmărește~~ și ~~aria zonei cu valoarea maximă. Apoi, rezultatele sunt scrise într-un fișier de ieșire~~.		Acest program prelucrează date de intrare din fișierul "meteoriti.in", verifică dacă datele de intrare sunt valide și determină cea mai mare zonă de teren afectată de meteorit și numărul total de zone afectate într-un teren reprezentat prin matricea a.

			Funcția "is_valid" verifică dacă dimensiunile matricei și numărul de evenimente sunt în intervalul specificat și dacă coordonatele și intensitățile meteoritilor sunt, de asemenea, în intervalul specificat.

			Funcția "build" construiește matricea a prin adunarea sumei în direcția verticală și orizontală, astfel încât a[i][j] să conțină suma de la (0,0) la (i,j) în matricea de intrare.

			Funcția "inside" verifică dacă coordonatele sunt în interiorul matricei.

			Funcția "fill" utilizează o parcurgere BFS (Breadth-First-Search) pentru a găsi cea mai mare zonă continuă de teren cu aceeași înălțime în jurul unui punct dat din matricea a. Aceasta returnează numărul de celule din zona respectivă.

			Funcția "solve" utilizează funcția "fill" pentru a căuta zonele de teren cu aceeași înălțime și pentru a determina cea mai mare zonă de teren afectată de meteorit și numărul total de zone afectate. Rezultatele sunt afișate în fișierul "meteoriti.out".

			În funcția principală, datele de intrare sunt citite din fișierul "meteoriti.in", verificate și prelucrate prin funcțiile "build" și "solve".

Cata at 07:56, 28 April 2023

2023-04-28T07:56:49Z

← Older revision		Revision as of 07:56, 28 April 2023
Line 9:		Line 9:
	==Date de ieșire==		==Date de ieșire==
	În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.		În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.
			În consolă se va afișa un mesaj de validare a datelor.
	==Restricții și precizări==		==Restricții și precizări==
	* 4 ≤ N, M ≤ 2.000		* 4 ≤ N, M ≤ 2.000
Line 24:		Line 24:
	* NU este bine să îl supărați pe vrăjitor!		* NU este bine să îl supărați pe vrăjitor!
	==Exemplu==		==Exemplu==
	meteoriti.in		; meteoriti.in
			: 5 6 7
	5 6 7		: 2 2 4 3 1
	2 2 4 3 1		: 4 4 4 6 2
	4 4 4 6 2		: 1 5 4 6 1
	1 5 4 6 1		: 2 5 3 6 1
	2 5 3 6 1		: 2 3 4 3 1
	2 3 4 3 1		: 5 1 5 3 3
	5 1 5 3 3		: 4 2 4 2 1
	4 2 4 2 1

	~~meteoriti.out~~

	~~3 12~~

			; meteoriti.out
			: 3 12
			; Consolă
			: Input valid
	==Explicație==		==Explicație==
	Matricea după meteoriţi:		Matricea după meteoriţi:
Line 55:		Line 54:
	dc = [0, 1, 0, -1]		dc = [0, 1, 0, -1]

	def is_valid(n, m, k~~, meteorites~~):
			def is_valid(n, m, k):
	if not(4 <= n <= 2000) or not(4 <= m <= 2000):		if not(4 <= n <= 2000) or not(4 <= m <= 2000):
	return False		return False
Line 67:		Line 67:
	return False		return False
	return True		return True


	def build():		def build():
Line 76:		Line 77:
	for j in range(1, m):		for j in range(1, m):
	a[i][j] += a[i][j-1]		a[i][j] += a[i][j-1]


	def inside(x, y):		def inside(x, y):
	return (0 <= x < n) and (0 <= y < m)		return (0 <= x < n) and (0 <= y < m)


	def fill(i, j, hmax):		def fill(i, j, hmax):
Line 94:		Line 97:
	q.append((iv, jv))		q.append((iv, jv))
	return area		return area


	def solve():		def solve():
Line 111:		Line 115:
	with open('meteoriti.out', 'w') as f:		with open('meteoriti.out', 'w') as f:
	f.write(f"{amax} {area0}")		f.write(f"{amax} {area0}")


	if __name__=="__main__":		if __name__=="__main__":
	with open('meteoriti.in', 'r') as f:		with open('meteoriti.in', 'r') as f:
	n, m, k = map(int, f.readline().split())		n, m, k = map(int, f.readline().split())
			if not is_valid(n,m,k):
			print("Input invalid")
			else:
			print("Input valid")
	a = [[0] * (nmax + 1) for _ in range(nmax + 1)]		a = [[0] * (nmax + 1) for _ in range(nmax + 1)]
	was_here = [[False] * (nmax + 1) for _ in range(nmax + 1)]		was_here = [[False] * (nmax + 1) for _ in range(nmax + 1)]

Cata: Pagină nouă: Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare rep...

2023-04-20T18:49:29Z

Pagină nouă: Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare rep...

New page

Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.

==Cerința==
Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).

==Date de intrare==
Pe prima linie a fișierului meteoriti.in se află trei numere naturale separate prin spațiu: N și M, reprezentând dimensiunile plantației și R, reprezentând numărul de reprize de meteoriți. Pe următoarele R linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C, unde r1 c1 reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2 coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.

==Date de ieșire==
În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.

==Restricții și precizări==
* 4 ≤ N, M ≤ 2.000
* 1 ≤ R ≤ 100.000
* 1 ≤ r1 ≤ r2 ≤ N
* 1 ≤ c1 ≤ c2 ≤ M
* 1 ≤ C ≤ 20.000
* Două celule se consideră vecine dacă au cel puțin o latură comună.
* Înălțimea inițială a celulelor se consideră 0.
* Se garantează că pentru 30% din teste 4 ≤ N, M ≤ 300 și 1 ≤ R ≤ 300
* Pentru rezolvarea corectă a primei cerinţe se acordă 80% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 20% din punctajul pe testul respectiv
* Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
* Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
* NU este bine să îl supărați pe vrăjitor!
==Exemplu==
meteoriti.in

5 6 7
2 2 4 3 1
4 4 4 6 2
1 5 4 6 1
2 5 3 6 1
2 3 4 3 1
5 1 5 3 3
4 2 4 2 1

meteoriti.out

3 12

==Explicație==
Matricea după meteoriţi:
0 0 0 0 1 1
0 1 2 0 2 2
0 1 2 0 2 2
0 2 2 2 3 3
3 3 3 0 0 0

Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3 este tot 3

==Rezolvare==
<syntaxhighlight lang="python">
nmax = 2*10**3
dl = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def is_valid(n, m, k, meteorites):
if not(4 <= n <= 2000) or not(4 <= m <= 2000):
return False
if not(1 <= k <= 100000):
return False
for i in range(k):
r1, c1, r2, c2, x = meteorites[i]
if not(1 <= r1 <= r2 <= n) or not(1 <= c1 <= c2 <= m):
return False
if not(1 <= x <= 20000):
return False
return True

def build():
global a
for j in range(m):
for i in range(1, n):
a[i][j] += a[i-1][j]
for i in range(n):
for j in range(1, m):
a[i][j] += a[i][j-1]

def inside(x, y):
return (0 <= x < n) and (0 <= y < m)

def fill(i, j, hmax):
global was_here
q = [(i, j)]
was_here[i][j] = True
area = 1
while q:
f1, f2 = q.pop(0)
for p in range(4):
iv, jv = f1+dl[p], f2+dc[p]
if inside(iv, jv) and a[iv][jv] == hmax and not was_here[iv][jv]:
area += 1
was_here[iv][jv] = True
q.append((iv, jv))
return area

def solve():
global was_here
hmax, amax, area0 = 0, 0, 0
for i in range(n):
for j in range(m):
if a[i][j] >= hmax and not was_here[i][j]:
area = fill(i, j, a[i][j])
if a[i][j] == hmax:
amax = max(amax, area)
else:
amax = area
hmax = max(hmax, a[i][j])
if not a[i][j]:
area0 += 1
with open('meteoriti.out', 'w') as f:
f.write(f"{amax} {area0}")

if __name__=="__main__":
with open('meteoriti.in', 'r') as f:
n, m, k = map(int, f.readline().split())
a = [[0] * (nmax + 1) for _ in range(nmax + 1)]
was_here = [[False] * (nmax + 1) for _ in range(nmax + 1)]
for i in range(k):
r1, c1, r2, c2, x = map(int, f.readline().split())
r1, r2 = r1 - 1, r2 - 1
c1, c2 = c1 - 1, c2 - 1
# Marks on matrix
a[r1][c1] += x
a[r1][c2 + 1] -= x
a[r2 + 1][c1] -= x
a[r2 + 1][c2 + 1] += x
build()
solve()

</syntaxhighlight>

==Explicație cod==
Acest cod este o soluție a unui problema de tip algoritmica, numită "Meteoriți", care implică procesarea unei matrici mari și determinarea unor proprietăți ale acesteia. Scopul problemei este de a găsi aria celui mai mare grup de celule în care valorile din matrice sunt egale și, de asemenea, de a găsi numărul de celule din matrice care au valoarea 0. Intrarea constă în dimensiunile matricei, numărul de meteorite care lovesc matricea și informații despre locul și efectul fiecărui meteorit. Matricea este actualizată în funcție de locurile în care loviturile de meteorit au avut loc. Codul utilizează o abordare de căutare în lățime pentru a determina aria celor mai mari zone în care valorile sunt egale și urmărește și aria zonei cu valoarea maximă. Apoi, rezultatele sunt scrise într-un fișier de ieșire.