View source for 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==
<syntaxhighlight lang="python" line>
#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()
</syntaxhighlight>