4051 - Lumina - Revision history

Andrada378: /* Explicație */

2024-01-05T20:33:15Z

Explicație

← Older revision		Revision as of 20:33, 5 January 2024
Line 39:		Line 39:
	2 5		2 5

	== Explicație ==		=== Explicație ===
	Se inversează rândul 2 și coloanele 2 și 5.		Se inversează rândul 2 și coloanele 2 și 5.

Line 55:		Line 55:
	NU		NU

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

	== Rezolvare ==		== 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):		def schimba_randuri_coloane(matrice, randuri, coloane):
			randuri_schimbate = []
			coloane_schimbate = []

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

	for i in range(randuri):		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

	~~if matrice[i][0] == 0:~~		return matrice, randuri_schimbate, coloane_schimbate

	~~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):		def all_lights_on(matrice, randuri, coloane):
			for randuri in matrice:
	for randuri in matrice:		if 0 in randuri:
			return False
	if 0 in randuri:		return True

	return False

	return True

	def rezolva_luminile():		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)

	~~n, m = map(int, input().split())~~		if all_lights_on(matrice, n, m):
			print("DA")
	~~matrice = [list(map(int, input().split())) for _ in range(n)]~~		print(" ".join(map(str, randuri_schimbate)))
			print(" ".join(map(str, coloane_schimbate)))
	~~matrice, randuri_schimbate,coloane_schimbate = schimba_randuri_coloane(matrice, n, m)~~		else:
			print("NU")
	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()		if __name__=="__main__":
			rezolva_luminile()
			</syntaxhighlight>

Andrada378 at 20:14, 2 January 2024

2024-01-02T20:14:30Z

← Older revision		Revision as of 20:14, 2 January 2024
Line 1:		Line 1:
	~~<u>~~''~~Cerinta~~''~~</u>~~		== '''Cerința''' ==

	Se consideră un panou de dimensiuni n×m		Se consideră un panou de dimensiuni n×m

	pe care sunt așezate nm		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:

	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 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).
	);

	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.		Găsiți o secvență cu un număr minim de comenzi care conduce la aprinderea tuturor becurilor.

	~~<u>''~~Date de intrare~~''</u>~~		== 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).

	~~Pe prima~~ linie se ~~află~~ numerele n		== 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.

	~~și m~~		== Restricții si precizări ==

	~~. Pe a i~~		* 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ă

	~~-a dintre următoarele n~~		== Exemplu1 ==
			'''Intrare'''

	~~linii se găsește o secvență de m~~		2 5

	~~numere care sunt fie~~ 0		1 0 1 1 0

	~~, fie~~ 1		0 1 0 0 1

	~~. Al j~~		'''Iesire'''

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

	.		2

	~~''<u>Date de iesire</u>''~~		2 5

	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~~		== Explicație ==
			Se inversează rândul 2 și coloanele 2 și 5.

	~~Pentru alte 10 de puncte, se garantează că soluția optimă inversează un rând și o coloană~~		== Exemplu 2: ==
			'''Intrare'''
	~~<u>~~''~~Exemplu1~~''~~</u>~~

	~~Intrare~~

	2 5		2 5

	1 0 1 1 0		1 0 1 1 1

	0 1 0 0 1		0 1 0 0 1

	~~Iesire~~		'''Ieșire'''

	DA		NU

	2

	~~2 5~~

	~~''<u>Rezolvare</u>''~~		== Explicație ==
			Se poate demonstra că nu există soluție pentru acest test.

			== Rezolvare ==
	def schimba_randuri_coloane(matrice, randuri, coloane):		def schimba_randuri_coloane(matrice, randuri, coloane):

Andrada378: Pagină nouă: ''Cerinta'' 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...

2023-12-16T17:18:43Z

Pagină nouă: ''Cerinta'' 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...

New page

''Cerinta''

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 m

numere care sunt fie 0

, fie 1

. Al j

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

.

''Date de iesire''

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.

''Restrictii si precizari''

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

''Rezolvare''

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