3513 - Covoare1: Difference between revisions

Revision as of 11:20, 27 December 2023

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 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

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

1 ⩽ n, m ⩽ 1.000.000
p ⩽ 200.000

Exemplul 1

covoare1in.txt: 7 8 9; 4 2; 2 4; 5 2; 1 4; 3 3; 2 1; 3 2; 2 3; 1 3

covoare1out.txt: 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

covoare1in.txt: -3 -2 2; 6 2; 0 -10

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> import heapq

def solve(n, m, p, carpets):

   # Initializare heap cu covoare
   heapq.heapify(carpets)

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

   return result

Citire date de intrare

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)]

Rezolvare

result = solve(n, m, p, carpets)

Scriere date de ieșire

with open("covoare1out.txt", "w") as output_file:

   for coord in result:
       output_file.write(f"{coord[0]} {coord[1]}\n")

</syntaxhighlight>

@@ Line 55: / Line 55: @@
 == Rezolvare ==
 <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>