Soluții trimise

Rezumat problemă

O matrice pătratică de dimensiuni N * N cu N par și elemente din mulțimea {0,1} se numește tablă de șah dacă oricare două celule vecine pe o linie sau pe o coloană au valori diferite (cu alte cuvinte, dacă nu există două valori egale alăturate).

De ziua ei, Victor i-a cumpărat Elisabetei o astfel de matrice A, care nu este neapărat tablă de șah. Aflând despre pasiunea ei, acesta vrea acum să transforme matricea A într-o tablă de șah. Timpul fiind limitat, el poate efectua doar următoarele tipuri de operații asupra matricei:
1. Interschimbă liniile i și j din A (celelalte linii rămân neschimbate, iar valorile din interiorul liniilor i și j rămân neschimbate și își păstrează ordinea). Operația are sens pentru 1 ≤ i, j ≤ N.
2. Interschimbă coloanele i și j din A (celelalte coloane rămân neschimbate, iar valorile din interiorul coloanelor i și j rămân neschimbate și își păstrează ordinea). Operația are sens pentru 1 ≤ i, j ≤ N.

Dorind s-o impresioneze pe Elisabeta, Victor apelează la voi, programatori renumiți, să-l ajutați în a transforma matricea A într-o tablă de șah. Pentru aceasta, Victor are nevoie de următoarele informații:
1. Poate fi transformată matricea A în tablă de șah?
2. Care este numărul minim de operații necesare pentru a duce la îndeplinire acest scop?
3. Care ar fi o succesiune de operații care transformă matricea A într-o tablă de șah?

OJI 2021, clasele XI-XII

ID   Utilizator Problema Data încărcării Stare
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 19:50 Evaluare finalizată 40
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:53 Evaluare finalizată 100
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:52 Evaluare finalizată 100
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:51 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:49 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:47 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:47 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:37 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:37 Evaluare finalizată 0
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 17:34 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 16:37 Evaluare finalizată 74
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 13:03 Evaluare finalizată 46
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 12:12 Evaluare finalizată 46
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 12:10 Evaluare finalizată 40
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 11:34 Evaluare finalizată 46
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 10:58 Evaluare finalizată 40
Adrian MODRISAN (dorulique) Polihroniade 12 Mai 2021, 10:01 Evaluare finalizată 0
Mihalache Sebastian (sebimih) Polihroniade 09 Mai 2021, 20:07 Evaluare finalizată 100
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 22:59 Evaluare finalizată 100
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 22:59 Evaluare finalizată 0
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 22:55 Evaluare finalizată 74
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 22:37 Evaluare finalizată 74
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 22:36 Evaluare finalizată 74
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 21:36 Evaluare finalizată 40
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 21:12 Evaluare finalizată 40
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 21:01 Evaluare finalizată 0
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 21:01 Evaluare finalizată 0
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 20:57 Evaluare finalizată 15
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 20:57 Evaluare finalizată 15
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 20:56 Evaluare finalizată 0
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 20:56 Evaluare finalizată 0
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 20:55 Evaluare finalizată 0
Teodorescu George (T_george_T) Polihroniade 08 Mai 2021, 20:49 Evaluare finalizată 15
Trufas Dafina (TrufasDafina) Polihroniade 25 Aprilie 2021, 16:31 Evaluare finalizată 0
Trufas Dafina (TrufasDafina) Polihroniade 25 Aprilie 2021, 15:48 Evaluare finalizată 0
cioclov maria (cioclovmariasimona) Polihroniade 25 Aprilie 2021, 01:25 Evaluare finalizată 52
cioclov maria (cioclovmariasimona) Polihroniade 25 Aprilie 2021, 01:24 Evaluare finalizată 40
cioclov maria (cioclovmariasimona) Polihroniade 25 Aprilie 2021, 01:19 Evaluare finalizată 40
cioclov maria (cioclovmariasimona) Polihroniade 25 Aprilie 2021, 00:45 Evaluare finalizată 40
cioclov maria (cioclovmariasimona) Polihroniade 24 Aprilie 2021, 22:35 Evaluare finalizată 40
cioclov maria (cioclovmariasimona) Polihroniade 24 Aprilie 2021, 22:00 Evaluare finalizată 0
cioclov maria (cioclovmariasimona) Polihroniade 22 Aprilie 2021, 14:42 Evaluare finalizată 0
cioclov maria (cioclovmariasimona) Polihroniade 22 Aprilie 2021, 00:26 Evaluare finalizată 0
cioclov maria (cioclovmariasimona) Polihroniade 22 Aprilie 2021, 00:25 Evaluare finalizată 0
dapi dipi (Dapi) Polihroniade 19 Aprilie 2021, 21:34 Evaluare finalizată 0
dapi dipi (Dapi) Polihroniade 19 Aprilie 2021, 21:31 Evaluare finalizată 0
dapi dipi (Dapi) Polihroniade 19 Aprilie 2021, 21:29 Evaluare finalizată 0
dapi dipi (Dapi) Polihroniade 19 Aprilie 2021, 21:23 Evaluare finalizată 0
dapi dipi (Dapi) Polihroniade 19 Aprilie 2021, 21:11 Evaluare finalizată 0
dapi dipi (Dapi) Polihroniade 19 Aprilie 2021, 16:22 Evaluare finalizată E.C