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

import heapq

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

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

    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
with open("covoare1in.txt", "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 = rezolva(n, m, p, covoare)

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

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