Editing 4051 - Lumina

<u>''Cerinta''</u>

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.

<u>''Date de intrare''</u>

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 m

numere care sunt fie 0

, fie 1

. Al j

-lea număr reprezintă starea becului (i,j)

.

''<u>Date de iesire</u>'' 

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.

<u>''Restrictii si precizari''</u>

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ă

<u>''Exemplu1''</u>

Intrare

2 5

1 0 1 1 0

0 1 0 0 1

Iesire

DA

2

2 5

''<u>Rezolvare</u>''

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

rezolva_luminile()