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

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()