0602 - Regine

Cerința

Pe o tablă de șah de dimensiune n se află m regine. O regină atacă o altă regină dacă cele două se află pe aceeași linie, coloană sau diagonală și între ele nu se află alte regine. Determinați numărul maxim p de regine care sunt atacate de o aceeași regină și numărul q de regine care atacă p alte regine.

Date de intrare

Fișierul de intrare reginein.txt conține pe prima linie numerele n m; următoarele m linii conțin perechi i j reprezentând linia și coloana unde se află poziționată o regină.

Date de ieșire

Fișierul de ieșire regine.out va conține pe prima linie numerele p q, separate prin exact un spațiu, reprezentând valorile de mai sus.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• 1 ⩽ m ⩽ 500
• 1 ⩽ i,j ⩽ n
• pe tablă nu există două regine suprapuse

Exemplu 1

reginein.txt

8 9

1 7

2 2

2 8

4 1

5 2

5 5

5 8

7 2

7 7

regineout.txt

5 3

Exemplu 2

Intrare

0 0

0 0

Ieșire

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 0602 - Regine

def is_valid_input(n, m, positions):

   if not (1 <= n <= 100 and 1 <= m <= 500):
       return False

   seen_positions = set()

   for i, j in positions:
       if not (1 <= i <= n and 1 <= j <= n) or (i, j) in seen_positions:
           return False
       seen_positions.add((i, j))

   return True

def count_attacked_queens(n, positions):

   attacked_by = [0] * len(positions)

   for i, (x, y) in enumerate(positions):
       for j, (u, v) in enumerate(positions):
           if i != j and (x == u or y == v or abs(x - u) == abs(y - v)):
               attacked_by[i] += 1

   max_attacked = max(attacked_by)
   num_queens_attacking_max = attacked_by.count(max_attacked)

   return max_attacked, num_queens_attacking_max

if __name__ == "__main__":

   with open("reginein.txt", "r") as file:
       n, m = map(int, file.readline().split())
       positions = [tuple(map(int, line.split())) for line in file]

   if is_valid_input(n, m, positions):
       p, q = count_attacked_queens(n, positions)
       with open("regineout.txt", "w") as output_file:
           output_file.write(f"{p} {q}\n")
   else:
       print("Nu au fost respectate cerintele impuse.")

</syntaxhighlight>