1751 - Icsuri

Cerința

În clasa a IX-a A sunt M elevi, numerotați de la 1 la M și fiecare are un număr preferat P. Plictisiți de ora de informatică, au inventat următorul joc:

pe o foaie de matematică desenează o tablă de joc de dimensiune N, formată din N linii și N coloane, numerotate de la 1 la N; fiecare linie și fiecare coloană are câte N pătrățele fiecare elev alege un pătrățel și desenează un X centrat în pătrățelul ales, fiecare din cele 4 laturi având cel mult P pătrățele desenate, fără a ieși de pe tabla de joc (să nu mâzgălească banca!!). icsurile desenate de elevi se pot suprapune. Cunoscând dimensiunea N a tablei de joc, numărul M de elevi, coordonatele alese de fiecare elev și numărul preferat al fiecărui elev, determinați câte pătrățele de pe tablă rămân nedesenate.

Date de intrare

Programul citește de la tastatură numărul N M, iar apoi M triplete i j p, reprezentând coordonatele pătrățelului ales și numărul preferat de fiecare elev.

Date de ieșire

Programul va afișa pe ecran numărul de pătrățele nedesenate.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 100000
• 1 ≤ i,j ≤ N
• 0 ≤ p ≤ N/2

Exemplu 1

Intrare

10 5
1 2 1
6 6 3
7 3 2
2 5 2
9 8 3

Iesire

62

Rezolvare

<syntaxhighlight lang="python" line> def citire_date():

   import sys
   input = sys.stdin.read
   data = input().split()
   N = int(data[0])
   M = int(data[1])
   elevi = []
   index = 2
   for _ in range(M):
       i = int(data[index])
       j = int(data[index+1])
       p = int(data[index+2])
       elevi.append((i, j, p))
       index += 3
   return N, M, elevi

def deseneaza_patratele(N, elevi):

   tabla = [[0] * N for _ in range(N)]
   for i, j, p in elevi:
       for x in range(max(0, i - p), min(N, i + p + 1)):
           for y in range(max(0, j - p), min(N, j + p + 1)):
               if abs(x - i) + abs(y - j) <= p:
                   tabla[x][y] = 1
   numar_patratele_nedesenate = sum(row.count(0) for row in tabla)
   return numar_patratele_nedesenate

def main():

   N, M, elevi = citire_date()

   # Verificarea restrictiilor
   assert 1 <= N <= 1000, "N trebuie sa fie intre 1 si 1000"
   assert 1 <= M <= 100000, "M trebuie sa fie intre 1 si 100000"
   for i, j, p in elevi:
       assert 1 <= i <= N, "i trebuie sa fie intre 1 si N"
       assert 1 <= j <= N, "j trebuie sa fie intre 1 si N"
       assert 0 <= p <= N // 2, "p trebuie sa fie intre 0 si N//2"

   rezultat = deseneaza_patratele(N, elevi)
   print(rezultat)

if __name__ == "__main__":

   main()

</syntaxhighlight>