Diferente pentru problema/matricen intre reviziile #3 si #15

Diferente intre titluri:

matricen
Matricen

Diferente intre continut:

== include(page="template/taskheader" task_id="matricen") ==
Anul acesta Mos Craciun v-a facut un cadou mai ciudat, anume o matrice binara $A$ cu $N$ linii si $N$ coloane. Totusi, matricile interesante sunt acele matrici care pe fiecare linie au numai elemente egale.
Dan Craciuc, fratele lui Mos Craciun va roaga sa il ajutati cu o problema pentru a va pune o vorba buna la mos. Dan va pune la dispozitie $Q$ submatrici ale matricei initiale si va roaga sa aflati pentru fiecare submatrice numarul minim de operatii care trebuie efectuate astfel incat submatricea rezultata in urma efectuarii operatiilor sa fie interesanta. In cadrul unei operatii puteti interschimba oricare doua elemente din submatrice. Dan va furnizeaza coltul stanga-sus al submatricei precum si coltul dreapta-jos al ei. Daca $(L1, C1)$ este coltul stanga-sus si $(L2, C2)$ este coltul dreapta jos, atunci submatricea este formata din elemetele $A{~i, j~}$
Anul acesta Mos Craciun v-a facut un cadou mai ciudat, anume o matrice binara $A$ cu $N$ linii si $N$ coloane. Totusi, matricele interesante sunt acele matrice care pe fiecare linie au numai elemente egale. Dan Craciun, fratele lui Mos Craciun va roaga sa il ajutati cu o problema pentru a va pune o vorba buna la mos. Dan va pune la dispozitie $Q$ submatrice ale matricei initiale si va roaga sa aflati pentru fiecare submatrice numarul minim de operatii care trebuie efectuate astfel incat submatricea rezultata in urma efectuarii operatiilor sa fie interesanta. In cadrul unei operatii puteti interschimba oricare doua elemente din submatrice. Dan va furnizeaza coltul stanga-sus al submatricei precum si coltul dreapta-jos al ei. Daca $(L1, C1)$ este coltul stanga-sus si $(L2, C2)$ este coltul dreapta jos, atunci submatricea este formata din elemetele $A{~i,j~}$, unde $L1 ≤ i ≤ L2$ si $C1 ≤ j ≤ C2$.
h2. Date de intrare
Fişierul de intrare $matricen.in$ ...
Fişierul de intrare $matricen.in$ contine pe prima linie doua numere naturale $N$ si $Q$, separate printr-un singur spatiu, avand seminificatia din enunt. Urmeaza apoi $N$ linii cu cate $N$ elemente $0$ sau $1$ reprezentand matricea $A$. Elementele unei linii sunt separate de cate un singur spatiu. In continuare se gasesc $Q$ linii reprezentand intrebarile lui Dan Craciun. Fiecare astfel de linie contine patru numere naturale $L1$, $C1$, $L2$ si $C2$, separate printr-un singur spatiu. Primele doua numere reprezinta linia si coloana corespunzatoare coltului stanga-sus al submatricei, iar ultimele doua linia si coloana coltului dreapta-jos.
h2. Date de ieşire
În fişierul de ieşire $matricen.out$ ...
În fişierul de ieşire $matricen.out$ veti afisa $Q$ linii, pe fiecare linia $i$ aflandu-se numarul minim de interschimbari ce trebuie realizat pentru cea de $i$-a submatrice din fisierul de intrare. Daca nu exista solutie se va afisa $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 300$
* $1 ≤ Q ≤ 50 000$
* Pentru $50%$ din teste $Q ≤ 1000$
h2. Exemplu
table(example). |_. matricen.in |_. matricen.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 3 3
  0 0 0
  0 1 0
  1 1 0
  2 1 3 3
  1 2 2 3
  1 1 1 3
| 1
  -1
  0
|
h3. Explicaţie
...
Pentru prima submatrice se poate interschimba elementul de pe pozitia $(2, 2)$ cu cel de pe pozitia $(3, 3)$. Pentru a doua submatrice nu avem solutie de aceea afisam $-1$. A treia submatrice contine deja o linie in care toate elementele sunt egale, deci nu mai trebuie sa efectuam nicio operatie.
== include(page="template/taskfooter" task_id="matricen") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
4845