Editing 3513 - Covoare1

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