1226 - Nebuni

Enunţ

Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.

O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.

Cerinţă

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.

Date de intrare

Fișierul de intrare nebuni.in conține pe prima linie numerele naturale N M, separate prin spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii sunt descrise poziţiile (linia şi coloana, separate prin spaţiu) celor M nebuni, câte un nebun pe o linie a fişierului.

Date de ieșire

Fișierul de ieșire nebuni.out va conține o singură linie pe care va fi scris un număr natural reprezentând numărul de poziţii sigure de pe tabla de şah.

Restricții și precizări

1 ≤ N ≤ 1 000 000 1 ≤ M < 16 500 Liniile şi coloanele sunt numerotate de la 1 la N. Pentru 50% dintre teste N ≤ 300. Pentru 60% dintre teste M ≤ 1000.

Exemplu 1

nebuni.in

5 4

2 1

1 3

4 2

5 2

nebuni.out

6

Exemplu 2

nebuni.in

10 3

1 1

15 8

5 12

nebuni.out

Date de intrare invalide.

Rezolvare

#1226 Nebuni
def verificare_date_intrare(N, M, nebuni):
  if not (1 <= N <= 1000000):
    return False
  if not (1 <= M < 16500):
    return False
  for x, y in nebuni:
    if not (1 <= x <= N and 1 <= y <= N):
      return False
  return True

def numar_pozitii_sigure(N, M, nebuni):
  # Inițializăm o matrice pentru tabla de șah și o marcam pe toate pozițiile atacate de nebuni
  tabla = [[False] * N for _ in range(N)]
  for x, y in nebuni:
    for i in range(N):
      for j in range(N):
        if abs(x - i) == abs(y - j):
          tabla[i][j] = True

  # Numărăm pozițiile sigure care nu sunt atacate de niciun nebun
  numar_pozitii_sigure = 0
  for i in range(N):
    for j in range(N):
      if not tabla[i][j]:
        numar_pozitii_sigure += 1

  return numar_pozitii_sigure

def main():
  # Citim datele de intrare
  try:
    with open("nebuni.in", "r") as fin:
      N, M = map(int, fin.readline().split())
      nebuni = [tuple(map(int, line.split())) for line in fin]
  except ValueError:
    # Date invalide
    with open("nebuni.out", "w") as fout:
      fout.write("Date invalide\n")
    return

  # Verificăm datele de intrare
  if not verificare_date_intrare(N, M, nebuni):
    with open("nebuni.out", "w") as fout:
      fout.write("Date de intrare invalide.\n")
    return

  # Determinăm numărul de poziții sigure
  rezultat = numar_pozitii_sigure(N, M, nebuni)

  # Scriem rezultatul în fișierul de ieșire
  with open("nebuni.out", "w") as fout:
    fout.write(str(rezultat) + "\n")

if __name__ == "__main__":
  main()