Ramona Dragoș: Pagină nouă: == 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 r...

2023-12-13T17:28:31Z

Pagină nouă: == 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 r...

New page

== 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>

0602 - Regine - Revision history