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

#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.")