0600 - Romburi

Cerința

Plictisindu-se la ora de matematică, Gigel a luat o foaie de pătrățele cu n linii și m coloane și a început să deseneze romburi, fiecare având forma din imagine și diferite dimensiuni. Este posibil ca unele romburi să fie incomplet desenate, datorită apropierii de marginea foii. În plus, unele romburi se pot suprapune. În felul acesta o parte dintre pătrățelele de pe foaie sunt colorate, altele sunt intacte. Pentru fiecare romb desenat (chiar incomplet), Gigel a notat pe altă foaie coordonatele (linie, coloană) colțului de sus și dimensiunea.

Determinați numărul de pătrățele de pe foaie care sunt intacte, după desenarea romburilor.

Date de intrare

Fișierul de intrare romburiin.txt conține pe prima linie numerele n m p. Următoarele p linii conțin numerele i j L, reprezentând un romb cu vârful de sus la coordonatele i j cu Lungimea laturii L.

Date de ieșire

Fișierul de ieșire romburiout.txt va conține pe prima linie numărul C de pătrățele intacte.

Restricții și precizări

• 1 ⩽ n,m, L ⩽ 1000
• 1 ⩽ p ⩽ 100

Exemplu 1

romburiin.txt

12 13 5

4 5 4

2 3 2

3 8 3

2 11 1

8 11 5

romburi.out

24

Exemplu 2

romburiin.txt

0 0 0

0 0 0

Ieșire

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 0600 - Romburi

def is_valid_input(n, m, L, p_list):

   if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= L <= 1000):
       return False

   if not (1 <= p <= 100 for _, _, _, p in p_list):
       return False

   return True

def count_intact_squares(n, m, L, p_list):

   intact_squares = n * m

   for i, j, L in p_list:
       top_left_row = max(0, i - L + 1)
       top_left_col = max(0, j - L + 1)
       bottom_right_row = min(n - 1, i + L - 1)
       bottom_right_col = min(m - 1, j + L - 1)

       intact_squares -= (bottom_right_row - top_left_row + 1) * (bottom_right_col - top_left_col + 1)

   return intact_squares

def main():

   with open("romburiin.txt", "r") as infile:
       n, m, p = map(int, infile.readline().split())
       p_list = [tuple(map(int, infile.readline().split())) for _ in range(p)]

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

   result = count_intact_squares(n, m, p, p_list)

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

if __name__ == "__main__":

   main()

</syntaxhighlight>