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>

1. 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>