Editing 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 &les; n &les; 100
*1 &les; m &les; 500
*1 &les; i,j &les; 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
<br>
== Exemplu 2 ==
; Intrare
: 0 0
: 0 0
; Ieșire
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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>