Editing 0604 - Maria

== Cerința ==
Maria dansează! Lecțiile de dans se desfășoară într-o sală imensă, împărțită în n*m sectoare pătratice cu dimensiunea 1, dispuse pe n linii și m coloane. În anumite sectoare se află diverse obstacole, astfel că acele sectoare nu pot fi utilizate pentru dans. Maria are nevoie pentru dans de o zonă dreptunghiulară de dimensiuni p, q, cu laturile paralele cu pereții sălii, care să nu conțină obstacole și vrea ca în fiecare zi să danseze într-o zonă diferită de cele în care a dansat deja. Determinați numărul de zile în care Maria poate dansa așa cum își dorește.
== Date de intrare ==
Fișierul de intrare mariain.txt conține pe prima linie numerele n m p q. A doua linie conține numărul k de sectoare din sală în care se află obstacole. Fiecare dintre următoarele k linii conține două numere i j, reprezentând linia și coloana unui sector ce conține un obstacol.
== Date de ieșire ==
Fișierul de ieșire mariaout.txt va conține pe prima linie numărul Z de zile în care Maria poate dansa în zone diferite.
== Restricții și precizări ==
*1 &les; n, m, p, q &les; 1000
*0 &les; k &les; 1000
*1 &les; i &les; n, 1 &les; j &les; m
*două zone de dans sunt distincte dacă diferă prin cel puțin un sector
*zona de dans poate fi orientată astfel încât să ocupe p linii și q coloane sau q linii și p coloane
== Exemplu 1 ==
;mariain.txt
:5 6 2 3
:3
:2 2
:3 5
:4 3
;mariaout.txt
:5
<br>
== Exemplu 2 ==
;mariain.txt
:0 -1 -2 0
:-1
:-3 -4
;mariaout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0604 - Maria
def is_valid_input(n, m, p, q, obstacles):
    if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= p <= 1000 and 1 <= q <= 1000):
        return False

    if not (0 <= len(obstacles) <= 1000):
        return False

    for i, j in obstacles:
        if not (1 <= i <= n and 1 <= j <= m):
            return False

    return True

def count_dance_days(n, m, p, q, obstacles):
    dance_days = 0

    for i in range(1, n - p + 2):
        for j in range(1, m - q + 2):
            valid_dance_zone = True

            for k in range(p):
                for l in range(q):
                    if (i + k, j + l) in obstacles:
                        valid_dance_zone = False
                        break

                if not valid_dance_zone:
                    break

            if valid_dance_zone:
                dance_days += 1

    for i in range(1, n - q + 2):
        for j in range(1, m - p + 2):
            valid_dance_zone = True

            for k in range(q):
                for l in range(p):
                    if (i + k, j + l) in obstacles:
                        valid_dance_zone = False
                        break

                if not valid_dance_zone:
                    break

            if valid_dance_zone:
                dance_days += 1

    return dance_days

def main():
    try:
        with open("mariain.txt", "r") as infile:
            n, m, p, q = map(int, infile.readline().split())
            k = int(infile.readline())
            obstacles = [tuple(map(int, infile.readline().split())) for _ in range(k)]
    except ValueError:
        print("Nu au fost respectate cerintele impuse.")
        return

    if not is_valid_input(n, m, p, q, obstacles):
        print("Nu au fost respectate cerintele impuse.")
        return

    result = count_dance_days(n, m, p, q, obstacles)

    with open("mariaout.txt", "w") as outfile:
        outfile.write(str(result))

if __name__ == "__main__":
    main()

</syntaxhighlight>