Fişierul intrare/ieşire:mapal.in, mapal.outSursăGrigore Moisil 2016, Clasele 11-12
AutorPetru TrimbitasAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mapal

Marele inginer NN a fost numit inspector general al barajelor. În prima zi de lucru el primeşte un sector dintr-un baraj de lângă un lac de acumulare care conţine stricăciuni şi are misiunea de a realiza un plan de reparaţii. În plus, costurile reparaţiilor trebuie să fie minime. Sectorul din baraj poate fi reprezentat ca o matrice binară de NxN. El a observat că liniile l1, l2, ..., lk şi coloanele c1, c2, ..., cl sunt singurele care au stricăciuni. Pentru a le repara el trebuie să înlocuiască unele elemente din matrice astfel încât liniile şi coloanele stricate să devină palindrom.
Ajutaţi-l pe NN să găsească numărul minim de înlocuiri şi să dovedească că e maestru în baraje de toate felurile.

Date de intrare

Pe prima linie a fişierului mapal.in se va afla N, reprezentând lăţimea şi lungimea barajului.
Pe următoarele N linii se vor afla N caractere, fiecare caracter aparţinând mulţimii {0, 1} şi reprezentând elementul de pe linia i şi coloana j a matricii care reprezintă barajul.
Pe următoarea linie se va afla L, reprezentând numărul de linii stricate. Pe următoarea linie se vor afla L numere reprezentând indicii liniilor stricate.
Pe următoarea linie se va afla C, reprezentând numărul de coloane stricate. Pe următoarea linie se vor afla C numere reprezentând indicii coloanelor stricate.

Date de ieşire

Pe singura linie a fişierului mapal.out se va afişa numărul minim de înlocuiri astfel încât liniile şi coloanele date să devină palindrom.

Restricţii

  • 1 ≤ N ≤ 1000
  • Elementele matricii aparţin mulţimii {0, 1}

Exemplu

mapal.inmapal.outExplicaţie
4
1011
0111
0000
1010
3
1 2 4
2
1 4
4
Una dintre soluţiile pentru care
liniile 1, 2, 4 şi coloanele 1, 4 sunt palindrom e:

1111
0110
0000
1111
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?