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>