3513 - Covoare1 - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T12:10:27Z

Rezolvare

← Older revision		Revision as of 12:10, 29 December 2023
Line 57:		Line 57:
	import heapq		import heapq

	def ~~solve~~(n, m, p, ~~carpets~~):		def rezolva(n, m, p, covoare):
	# Initializare heap cu covoare		# Initializare heap cu covoare
	heapq.heapify(~~carpets~~)		heapq.heapify(covoare)

	# Afișare coordonate în ordinea notată de Miguel		# Afișare coordonate în ordinea notată de Miguel
	~~result~~ = []		rezultat = []
	for _ in range(p):		for _ in range(p):
	~~top_carpets~~ = heapq.heappop(~~carpets~~)		top_covoare = heapq.heappop(covoare)
	~~result~~.append((~~top_carpets~~[0], ~~top_carpets~~[1]))		rezultat.append((top_covoare[0], top_covoare[1]))

	return ~~result~~		return rezultat

			def verifica_rezultat(input_file, output_file):
			# Citire date de intrare
			with open(input_file, "r") as f:
			n, m, p = map(int, f.readline().split())
			covoare = [tuple(map(int, f.readline().split())) for _ in range(p)]

			# Apelare funcție de rezolvare
			rezultat_obtinut = rezolva(n, m, p, covoare)

			# Citire rezultat așteptat
			with open(output_file, "r") as g:
			rezultat_asteptat = [tuple(map(int, linie.split())) for linie in g.readlines()]

			# Verificare rezultat
			if rezultat_obtinut == rezultat_asteptat:
			print("Rezultat corect!")
			else:
			print("Rezultat incorect!")
			print("Rezultat așteptat:")
			print(rezultat_asteptat)
			print("Rezultat obținut:")
			print(rezultat_obtinut)

	# Citire date de intrare		# Citire date de intrare
	with open("covoare1in.txt", "r") as ~~input_file~~:		with open("covoare1in.txt", "r") as f:
	n, m, p = map(int, ~~input_file~~.readline().split())		n, m, p = map(int, f.readline().split())
	~~carpets~~ = [tuple(map(int, ~~input_file~~.readline().split())) for _ in range(p)]		covoare = [tuple(map(int, f.readline().split())) for _ in range(p)]

	# ~~Rezolvare~~		# Apelare funcție de rezolvare
	~~result~~ = ~~solve~~(n, m, p, ~~carpets~~)		rezultat = rezolva(n, m, p, covoare)

	# Scriere date de ieșire		# Scriere date de ieșire
	with open("covoare1out.txt", "w") as ~~output_file~~:		with open("covoare1out.txt", "w") as g:
	for coord in ~~result~~:		for coord in rezultat:
	~~output_file~~.write(f"{coord[0]} {coord[1]}\n")		g.write(f"{coord[0]} {coord[1]}\n")

			# Apelare funcție de verificare
			verifica_rezultat("covoare1in.txt", "covoare1out.txt")

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T11:20:14Z

Rezolvare

← Older revision		Revision as of 11:20, 27 December 2023
Line 55:		Line 55:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	~~def rezolva(n, m, p, covoare):~~		import heapq
	~~# Funcție pentru a verifica dacă o anumită poziție este disponibilă pentru așezarea unui covor~~
	~~def este_disponibil(x, y, a, b):~~
	~~for i in range(x, x + a):~~
	~~for j in range(y, y + b):~~
	~~if room[i][j] == 1:~~
	~~return False~~
	~~return True~~

	~~# Funcție pentru a așeza un covor în încăpere~~		def solve(n, m, p, carpets):
	def ~~aseaza_covor~~(x, y, a, b):		# Initializare heap cu covoare
	~~for i in range(x, x + a):~~		heapq.heapify(carpets)
	~~for j in range~~(~~y, y + b~~):
	~~room[i][j] = 1~~

	# ~~Funcție pentru a găsi o poziție disponibilă~~ în ~~încăpere pentru așezarea unui covor~~		# Afișare coordonate în ordinea notată de Miguel
	~~def gaseste_pozitie_disponibila():~~		result = []
	for i in range(n):		for _ in range(p):
	~~for j in range~~(m):		top_carpets = heapq.heappop(carpets)
	~~if room~~[i][j] ~~== 0:~~		result.append((top_carpets[0], top_carpets[1]))
	~~return i, j~~

	~~# Inițializează o matrice pentru încăpere~~		return result
	~~room = [[0] * m for _ in range(n)]~~

	~~# Inițializează o listă pentru a stoca coordonatele colțului din stânga sus ale fiecărui covor~~		# Citire date de intrare
	~~rezultat~~ = []		with open("covoare1in.txt", "r") as input_file:
			n, m, p = map(int, input_file.readline().split())
			carpets = [tuple(map(int, input_file.readline().split())) for _ in range(p)]

	# ~~Parcurge fiecare covor~~		# Rezolvare
	~~for covor in covoare:~~		result = solve(n, m, p, carpets)
	a, ~~b = covor~~

	# ~~Găsește o poziție disponibilă pentru așezarea covorului~~		# Scriere date de ieșire
	~~pozitie = gaseste_pozitie_disponibila~~()		with open("covoare1out.txt", "w") as output_file:
			for coord in result:
			output_file.write(f"{coord[0]} {coord[1]}\n")

	~~# Verifică dacă poziția găsită este validă pentru așezarea covorului~~
	~~if este_disponibil(pozitie[0], pozitie[1], a, b):~~
	~~# Adaugă coordonatele colțului din stânga sus ale covorului la rezultat~~
	~~rezultat.append(pozitie)~~
	~~# Așează covorul în încăpere~~
	~~aseaza_covor(pozitie[0], pozitie[1], a, b)~~
	~~else:~~
	~~# Dacă nu se găsește o poziție validă, adaugă (-1, -1) la rezultat~~
	~~rezultat.append((-1, -1))~~

	~~return rezultat~~

	~~def main():~~
	~~# Deschide fișierul de intrare~~
	~~with open("covoare1.txt", "r") as f_in:~~
	~~n, m, p = map(int, f_in.readline().split())~~
	~~covoare = [tuple(map(int, f_in.readline().split())) for _ in range(p)]~~

	~~# Rezolvă problema~~
	~~rezultat = rezolva(n, m, p, covoare)~~

	~~# Deschide fișierul de ieșire~~
	~~with open("covoare1.txt", "w") as f_out:~~
	~~# Scrie rezultatul în fișierul de ieșire~~
	~~for r in rezultat:~~
	~~f_out.write(f"{r[0]} {r[1]}\n")~~

	~~if __name__ == "__main__":~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 11:18, 27 December 2023

2023-12-27T11:18:49Z

← Older revision		Revision as of 11:18, 27 December 2023
Line 1:		Line 1:
	== Cerinta ==		== Cerinta ==

	Se consideră o încăpere de lungime n și lățime m împărțită în n*m zone pătrate, sub forma unei matrici cu n linii și m coloane. Încăperea este acoperită în totalitate cu p covoare dreptunghice de diferite dimensiuni astfel încât acestea nu se suprapun, fiecare zonă pătrată a încăperii fiind acoperită de exact un covor.		Se consideră o încăpere de lungime '''n''' și lățime '''m''' împărțită în '''n*m''' zone pătrate, sub forma unei matrici cu n linii și m coloane. Încăperea este acoperită în totalitate cu p covoare dreptunghice de diferite dimensiuni astfel încât acestea nu se suprapun, fiecare zonă pătrată a încăperii fiind acoperită de exact un covor.

	Miguel, administratorul clădirii, este responsabil cu spălarea covoarelor. Astfel, el a notat dimensiunile fiecărui covor, în ordine, de sus în jos și de la stânga la dreapta. Covoarele au fost scoase și spălate, iar acum Miguel vrea să le pună la loc.		Miguel, administratorul clădirii, este responsabil cu spălarea covoarelor. Astfel, el a notat dimensiunile fiecărui covor, în ordine, de sus în jos și de la stânga la dreapta. Covoarele au fost scoase și spălate, iar acum Miguel vrea să le pună la loc.
Line 8:		Line 8:
	== Date de intrare ==		== Date de intrare ==

	Fișierul de intrare ~~covoare1~~.txt conține pe prima linie numerele n, m, p, iar pe următoarele p linii câte două numere a și b reprezentând lungimea (numărul de linii) și lățimea (numărul de coloane) fiecărui covor în ordinea notată de Miguel.		Fișierul de intrare '''covoare1in.txt''' conține pe prima linie numerele '''n, m, p''', iar pe următoarele '''p''' linii câte două numere a și b reprezentând lungimea (numărul de linii) și lățimea (numărul de coloane) fiecărui covor în ordinea notată de Miguel.

	== Date de iesire ==		== Date de iesire ==

	Fișierul de ieșire ~~covoare1~~.txt va conține p linii cu câte două numere ce reprezintă coordonatele colțului din stânga sus ale fiecărui covor, în ordinea notată de Miguel.		Fișierul de ieșire '''covoare1out.txt''' va conține '''p''' linii cu câte două numere ce reprezintă coordonatele colțului din stânga sus ale fiecărui covor, în ordinea notată de Miguel.

	== Restrictii si precizari ==		== Restrictii si precizari ==

	*1 ≤ n, m ≤ 1.000.000		*1 &les; n, m &les; 1.000.000
	*p ≤ 200.000		*p &les; 200.000

	== Exemplul 1 ==		== Exemplul 1 ==
	;~~Intrare~~		;covoare1in.txt
	:7 8 9		:7 8 9
	:4 2		:4 2
Line 32:		Line 32:
	:1 3		:1 3

	;~~Iesire~~		;covoare1out.txt
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:1 1		:1 1
	:1 3		:1 3
Line 45:		Line 45:

	== Exemplul 2 ==		== Exemplul 2 ==
	;~~Intrare~~		;covoare1in.txt
	:-3 -2 2		:-3 -2 2
	:6 2		:6 2
	:0 -10		:0 -10
	~~;Iesire~~
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: Pagină nouă: == Cerinta == Se consideră o încăpere de lungime n și lățime m împărțită în n*m zone pătrate, sub forma unei matrici cu n linii și m coloane. Încăperea este acoperită în totalitate cu p covoare dreptunghice de diferite dimensiuni astfel încât acestea nu se suprapun, fiecare zonă pătrată a încăperii fiind acoperită de exact un covor. Miguel, administratorul clădirii, este responsabil cu spălarea covoarelor. Astfel, el a notat dimensiunile fiecărui...

2023-12-13T11:49:34Z

Pagină nouă: == Cerinta == Se consideră o încăpere de lungime n și lățime m împărțită în n*m zone pătrate, sub forma unei matrici cu n linii și m coloane. Încăperea este acoperită în totalitate cu p covoare dreptunghice de diferite dimensiuni astfel încât acestea nu se suprapun, fiecare zonă pătrată a încăperii fiind acoperită de exact un covor. Miguel, administratorul clădirii, este responsabil cu spălarea covoarelor. Astfel, el a notat dimensiunile fiecărui...

New page

== Cerinta ==

Se consideră o încăpere de lungime n și lățime m împărțită în n*m zone pătrate, sub forma unei matrici cu n linii și m coloane. Încăperea este acoperită în totalitate cu p covoare dreptunghice de diferite dimensiuni astfel încât acestea nu se suprapun, fiecare zonă pătrată a încăperii fiind acoperită de exact un covor.

Miguel, administratorul clădirii, este responsabil cu spălarea covoarelor. Astfel, el a notat dimensiunile fiecărui covor, în ordine, de sus în jos și de la stânga la dreapta. Covoarele au fost scoase și spălate, iar acum Miguel vrea să le pună la loc.
Cunoscând dimensiunile încăperii, numărul de covoare precum și dimensiunile fiecărui covor în ordinea in care Miguel le-a notat, să se afișeze coordonatele colțului din stânga sus ale fiecărui covor, în ordinea notată de Miguel, adică in ordine lexicografică.

== Date de intrare ==

Fișierul de intrare covoare1.txt conține pe prima linie numerele n, m, p, iar pe următoarele p linii câte două numere a și b reprezentând lungimea (numărul de linii) și lățimea (numărul de coloane) fiecărui covor în ordinea notată de Miguel.

== Date de iesire ==

Fișierul de ieșire covoare1.txt va conține p linii cu câte două numere ce reprezintă coordonatele colțului din stânga sus ale fiecărui covor, în ordinea notată de Miguel.

== Restrictii si precizari ==

*1 ≤ n, m ≤ 1.000.000
*p ≤ 200.000

== Exemplul 1 ==
;Intrare
:7 8 9
:4 2
:2 4
:5 2
:1 4
:3 3
:2 1
:3 2
:2 3
:1 3

;Iesire
;Datele introduse corespund restrictiilor impuse
:1 1
:1 3
:1 7
:3 3
:4 3
:4 6
:5 1
:6 6
:7 3

== Exemplul 2 ==
;Intrare
:-3 -2 2
:6 2
:0 -10
;Iesire
;Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def rezolva(n, m, p, covoare):
# Funcție pentru a verifica dacă o anumită poziție este disponibilă pentru așezarea unui covor
def este_disponibil(x, y, a, b):
for i in range(x, x + a):
for j in range(y, y + b):
if room[i][j] == 1:
return False
return True

# Funcție pentru a așeza un covor în încăpere
def aseaza_covor(x, y, a, b):
for i in range(x, x + a):
for j in range(y, y + b):
room[i][j] = 1

# Funcție pentru a găsi o poziție disponibilă în încăpere pentru așezarea unui covor
def gaseste_pozitie_disponibila():
for i in range(n):
for j in range(m):
if room[i][j] == 0:
return i, j

# Inițializează o matrice pentru încăpere
room = [[0] * m for _ in range(n)]

# Inițializează o listă pentru a stoca coordonatele colțului din stânga sus ale fiecărui covor
rezultat = []

# Parcurge fiecare covor
for covor in covoare:
a, b = covor

# Găsește o poziție disponibilă pentru așezarea covorului
pozitie = gaseste_pozitie_disponibila()

# Verifică dacă poziția găsită este validă pentru așezarea covorului
if este_disponibil(pozitie[0], pozitie[1], a, b):
# Adaugă coordonatele colțului din stânga sus ale covorului la rezultat
rezultat.append(pozitie)
# Așează covorul în încăpere
aseaza_covor(pozitie[0], pozitie[1], a, b)
else:
# Dacă nu se găsește o poziție validă, adaugă (-1, -1) la rezultat
rezultat.append((-1, -1))

return rezultat

def main():
# Deschide fișierul de intrare
with open("covoare1.txt", "r") as f_in:
n, m, p = map(int, f_in.readline().split())
covoare = [tuple(map(int, f_in.readline().split())) for _ in range(p)]

# Rezolvă problema
rezultat = rezolva(n, m, p, covoare)

# Deschide fișierul de ieșire
with open("covoare1.txt", "w") as f_out:
# Scrie rezultatul în fișierul de ieșire
for r in rezultat:
f_out.write(f"{r[0]} {r[1]}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>