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 ⩽ n, m, p, q ⩽ 1000
• 0 ⩽ k ⩽ 1000
• 1 ⩽ i ⩽ n, 1 ⩽ j ⩽ 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

Exemplu 2

mariain.txt

0 -1 -2 0

-1

-3 -4

mariaout.txt

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

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