0624 - Sah1

Cerința

Alex dorește să își învețe fratele să joace șah. După ce i-a explicat regulile, Alex vrea să vadă dacă fratele lui a înțeles, aşa că îi dă un mic test. Având o tablă de șah de N linii şi N coloane, Alex pune pe ea M ture (tura atacă doar pe coloana și linia pe care se află) și un rege. Apoi îi cere fratelui său să îi spună de câte ture este atacat regele în acel moment și pe câte căsuțe de pe tablă poate fi pus regele, astfel încât să nu se afle în șah.

În figura de mai jos avem trei ture şi un rege. Regele nu este atacat de nicio tură, fiindcă nu se află pe aceeaşi linie sau aceeaşi coloană cu niciuna dintre ele. Cunoscând dimensiunea N a tablei de șah, poziția regelui de pe tablă, numărul M de ture și poziția fiecărei ture de pe tablă, se cere:

a)să se afișeze numărul de ture care atacă regele în acel moment; b)numărul de poziții în care regele poate fi pus, astfel încât să nu fie atacat de vreo tură.

Date de intrare

Fişierul de intrare sah1.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află două numere naturale N și M, cu semnificația din enunț, pe linia a treia se află două numere naturale reprezentând poziția regelui pe tablă, iar pe fiecare dintre următoarele M linii se află câte două numere naturale reprezentând linia respectiv coloana unei ture.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, în fişierul de ieşire sah1.out se va scrie un număr natural reprezentând numărul de ture ce atacă regele.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, în fișierul de ieșire sah1.out se va scrie pe prima linie un număr natural Q, reprezentând numărul de poziții pe care poate fi pus regele astfel încât să nu fie atacat de vreo tură.

Restricții și precizări

• 2 ≤ N ≤ 10 000
• 0 ≤ M ≤ min(2 000, N2-1)
• Tabla de șah are liniile și coloanele numerotate de la 1 la N.
• Regele poate fi pus pe orice căsuță de pe tablă care nu este ocupată de o tură sau care nu este atacată de vreo tură.

Exemplu 1

Intrare

1
4 3
3 1
1 2
2 3
4 3

Iesire

0

Rezolvare

<syntaxhighlight lang="python" line> def solve_p1(N, king_pos, rooks):

   king_row, king_col = king_pos
   attacks = 0
   
   for rook_row, rook_col in rooks:
       if rook_row == king_row or rook_col == king_col:
           attacks += 1
           
   return attacks

def solve_p2(N, king_pos, rooks):

   king_row, king_col = king_pos
   safe_positions = 0

   for row in range(1, N + 1):
       for col in range(1, N + 1):
           if row == king_row and col == king_col:
               continue
           safe = True
           for rook_row, rook_col in rooks:
               if row == rook_row or col == rook_col:
                   safe = False
                   break
           if safe:
               safe_positions += 1
               
   return safe_positions

def main():

   with open('sah1.in', 'r') as f:
       data = f.read().splitlines()
   
   p = int(data[0].strip())
   N, M = map(int, data[1].strip().split())
   king_pos = tuple(map(int, data[2].strip().split()))
   rooks = [tuple(map(int, line.strip().split())) for line in data[3:3 + M]]

   # Restricții
   assert 2 <= N <= 10000, "N trebuie să fie între 2 și 10000"
   assert 0 <= M <= min(2000, N**2), "M trebuie să fie între 0 și min(2000, N**2)"
   assert 1 <= king_pos[0] <= N and 1 <= king_pos[1] <= N, "Poziția regelui trebuie să fie validă"
   for rook in rooks:
       assert 1 <= rook[0] <= N and 1 <= rook[1] <= N, "Pozițiile turelor trebuie să fie valide"

   if p == 1:
       # Rezolvăm punctul a)
       result = solve_p1(N, king_pos, rooks)
       with open('sah1.out', 'w') as f:
           f.write(f"{result}\n")
   elif p == 2:
       # Rezolvăm punctul b)
       result = solve_p2(N, king_pos, rooks)
       with open('sah1.out', 'w') as f:
           f.write(f"{result}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>