# PBinfo #3727 – Polihroniade – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț 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. Cerința 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? În cazul ultimei cerințe, pentru a intra în grațiile lui Victor va trebui ca numărul de operații efectuate să fie minim. Totuși, chiar și un număr neminim de operații va fi răsplătit, însă nu într-atât de mult. Vi se dau două numere P, T și T matrice A, reprezentând mai multe instanțe ale problemei. Pentru fiecare matrice A dintre cele T va trebui să rezolvați cerința cu numărul P∊{1,2,3} dintre cele listate mai sus. Date de intrare Pe prima linie se găsesc două numere întregi pozitive P și T, reprezentând numarul cerinței de rezolvat și, respectiv, numărul de scenarii pentru care va trebui să rezolvați problema. Urmează cele T instanțe ale problemei, fiecare fiind compusă din N + 1 linii: pe prima linie se va afla numarul N, iar pe următoarele N linii câte N cifre binare neseparate prin spații, reprezentând câte o linie a matricei A. Date de ieșire Pentru fiecare dintre cele T instanțe se va afișa răspunsul, începând de la o linie nouă, după cum urmează: 1. Dacă P = 1, atunci se va afișa pe o singură linie 1 dacă matricea A poate fi transformată în tablă de șah, și 0 altfel. 2. Dacă P = 2, atunci se va afișa pe o singură linie un întreg reprezentând numărul minim de interschimbări de linii și/sau coloane necesare pentru a transforma matricea A în tablă de șah. 3. Dacă P = 3, atunci se va afișa pe o linie un număr X. Apoi, pe fiecare dintre următoarele X linii se va afișa câte o interschimbare de linii sau coloane, după următorul format: L i j are semnificația că liniile i și j se interschimbă, iar C i j are semnificația că se interschimbă coloanele i și j. Matricea obținută după aplicarea celor X operații asupra lui A în ordinea dată trebuie să fie o tablă de șah. Restricții și precizări 1 ≤ T ≤ 350 1 ≤ N ≤ 1 000 N este par. Pentru cerințele de tip P = 2 și P = 3 se garantează că matricea A poate fi transformată în tablă de șah folosind interschimbări de linii și/sau coloane. Suma valorilor N pentru cele T scenarii nu depășește 2.000. Pentru 40 de puncte, P = 1 Pentru alte 34 de puncte, P = 2 Pentru alte 26 de puncte, P = 3 Dacă există mai multe soluții, oricare este considerată corectă. Dacă numărul X de operații folosite nu este minim, atunci se acordă 50% din punctajul pe test. Exemplul 1: Intrare 1 3 2 11 11 4 1100 1100 0011 0011 2 10 01 Ieșire 0 1 1 Explicație Avem P = 1, deci pentru cele T = 3 instanțe se cere numai dacă se pot transforma în tablă de șah prin interschimbări de linii și/sau coloane. Pentru prima instanță acest lucru nu este posibil, deoarece nu avem niciun 0 în matrice. Pentru cea de-a doua instanță, putem efectua următoarele operații: Pentru ultima instanță, matricea A este deja tablă de șah. Exemplul 2: Intrare 2 2 4 1100 1100 0011 0011 2 10 01 Ieșire 2 0 Explicație Pentru al doilea exemplu avem P = 2, deci pentru cele T = 2 instanțe se cere numărul minim de operații pentru a le transforma în tablă de șah. Pentru prima instanță, o soluție cu 2 operații este prezentată mai sus, și nu există soluții mai scurte. Pentru cea de-a doua instanță, matricea este deja tablă de șah, deci răspunsul este 0. Exemplul 3: Intrare 3 2 4 1100 1100 0011 0011 2 10 01 Ieșire 3 L 2 4 C 2 3 L 1 2 0 Explicație Al treilea exemplu este exact ca anteriorul, numai că avem P = 3, deci trebuie tipărite exact care sunt operațiile ce aduc matricea la forma de tablă de șah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu să afișăm o soluție cu 2 operații (adică număr minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o soluție compusa din 3 operații prin care obținem doar 50% din punctaj: ## Cod sursă C++ ```cpp /* Adrian Panaete - 100 puncte */ #include using namespace std; void solve(),afisare(char,vector&,vector&); int p,t,n,balans(string); bool ok; int main() { cin>>p>>t; for(;t;t--)solve(); return 0; } void solve() { ok=true; cin>>n; string s,L,C,LN; cin>>L; LN=L; for(auto &it:LN)it='1'-it+'0'; C.push_back(L[0]); for(int i=1;i>s; C.push_back(s[0]); if(s==L||s==LN) continue; ok=false; } if(balans(L)||balans(C))ok=false; if(p==1){cout< a[2][2],b[2][2]; for(int i=0;i &X,vector &Y) { int k=X.size(); for(int i=0;i