4051 - Lumina

Cerința

Se consideră un panou de dimensiuni n×m

pe care sunt așezate nm becuri. Becul de pe rândul i și coloana j se notează (i,j). Inițial, fiecare bec este stins (0) sau aprins (1). Putem efectua următoarele comenzi de oricâte ori:

Se alege un rând i(1≤i≤n) și se inversează starea tuturor becurilor de pe rândul i (0→1,1→0);
Se alege o coloană j (1≤j≤m) și se inversează starea tuturor becurilor de pe coloana j (0→1,1→0).

Găsiți o secvență cu un număr minim de comenzi care conduce la aprinderea tuturor becurilor.

Date de intrare

Pe prima linie se află numerele n și m. Pe a i-a dintre următoarele n linii se găsește o secvență de mnumere care sunt fie 0, fie 1. Al j-lea număr reprezintă starea becului (i,j).

Date de ieșire

Programul va afișa DA, dacă este posibilă aprinderea tuturor becurilor și NU în caz contrar. Dacă răspunsul este DA, pe a doua linie se vor afișa indicii liniilor inversate. Apoi, pe a treia linie se vor afișa indicii coloanelor inversate. Atât pe a doua, cât și pe a treia linie, numerele vor fi afișate în ordine crescătoare.

Restricții si precizări

2≤n,m≤500
Se garantează că pentru testele date, există o unică soluție optimă
Pentru 10 de puncte, se garantează că soluția optimă inversează doar rânduri
Pentru alte 10 de puncte, se garantează că soluția optimă inversează un rând și o coloană

Exemplu1

Intrare

2 5

1 0 1 1 0

0 1 0 0 1

Iesire

DA

2

2 5

Explicație

Se inversează rândul 2 și coloanele 2 și 5.

Exemplu 2:

Intrare

2 5

1 0 1 1 1

0 1 0 0 1

Ieșire

NU

Explicație

Se poate demonstra că nu există soluție pentru acest test.

Rezolvare

<syntaxhighlight lang="python"> def validare_date(n, m):

   if not (2 <= n <= 500) or not (2 <= m <= 500):
       raise ValueError("Dimensiunile matricei trebuie să fie între 2 și 500 inclusiv.")

def schimba_randuri_coloane(matrice, randuri, coloane):

   randuri_schimbate = []
   coloane_schimbate = []

   # Parcurgem toate liniile și coloanele și verificăm dacă becul trebuie inversat
   for i in range(randuri):
       if matrice[i][0] == 0:
           randuri_schimbate.append(i + 1)  # Adăugăm indexul rândului pentru a fi inversat
           for j in range(coloane):
               matrice[i][j] = 1 if matrice[i][j] == 0 else 0  # Inversăm starea becului

   for j in range(coloane):
       count = sum(matrice[i][j] for i in range(randuri))
       if count <= randuri // 2:
           coloane_schimbate.append(j + 1)  # Adăugăm indexul coloanei pentru a fi inversată
           for i in range(randuri):
               matrice[i][j] = 1 if matrice[i][j] == 0 else 0  # Inversăm starea becului

   return matrice, randuri_schimbate, coloane_schimbate

def all_lights_on(matrice, randuri, coloane):

   for randuri in matrice:
       if 0 in randuri:
           return False
   return True

def rezolva_luminile():

   n, m = map(int, input().split())
   matrice = [list(map(int, input().split())) for _ in range(n)]
   matrice, randuri_schimbate, coloane_schimbate = schimba_randuri_coloane(matrice, n, m)

   if all_lights_on(matrice, n, m):
       print("DA")
       print(" ".join(map(str, randuri_schimbate)))
       print(" ".join(map(str, coloane_schimbate)))
   else:
       print("NU")

if __name__=="__main__":

   rezolva_luminile()

</syntaxhighlight>