zone

Zone

== include(page="template/taskheader" task_id="zone") ==

Poveste si cerinta...

Fie o matrice patratica cu $N$ linii si $N$ coloane cu elemente numere naturale nenule. Matricea trebuie impartita in noua regiuni astfel: se aleg doua linii {$l{~1~}$} si {$l{~2~}$} si doua coloane {$c{~1~}$} si {$c{~2~}$}, {$1 &le; l{~1~} < l{~2~} < N$}, {$1 &le; c{~1~} < c{~2~} < N$} si se _taie_ matricea de-alungul acestor linii, respectiv coloane, ca in figura de mai jos:
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; !problema/zone?image001.jpg!
 
Se observa ca zonele {$1$}, $4$ si $7$ sunt formate din toate elementele de pe primele $c{~1~}$ coloane, zonele {$2$}, $5$ si $8$ sunt cuprinse intre coloanele {$c{~1~}+1$} si {$c{~2~}$}, iar zonele {$3$}, {$6$}, {$9$} sunt intre coloanele {$c{~2~}+1$} si {$N$}. Similar, zonele {$1$}, $2$ si $3$ sunt intre liniile {$1$} si {$l{~1~}$}, {$4$}, {$5$} si $6$ intre {$l{~1~}+1$} si {$l{~2~}$}, iar zonele {$7$}, {$8$} si {$9$} intre liniile {$l{~2~}+1$} si {$N$}. Se noteaza intr-o ordine oarecare sumele elementelor pentru fiecare regiune din cele noua astfel formate.
Sa se determine liniile {$l{~1~}$} si {$l{~2~}$} si coloanele {$c{~1~}$} si {$c{~2~}$} astfel incat sa se formeze cele noua sume date.

h2. Date de intrare

...

Fisierul de intrare $zone.in$ contine pe prima linie numarul natural {$N$}, dimensiunea matricii. A doua linie contine noua numere naturale, sumele regiunilor date intr-o ordine oarecare. Fiecare din urmatoarele {$N$} linii contine cate {$N$} numere naturale nenule, elementele matricii.
Recomandam sa folositi scanf pentru citire si nu cin.

h2. Date de iesire

...

Fisierul de iesire $zone.out$ va contine o singura linie pe care se afla patru numere naturale, {$l{~1~}$}, {$l{~2~}$}, {$c{~1~}$} si {$c{~2~}$}, despartite de exact un spatiu, reprezentand solutia problemei. Daca sunt mai multe solutii posibile se va afisa cea in care {$l{~1~}$} este minim posibila. Daca si in acest caz exista mai multe solutii posibile, se va afisa cea in care {$c{~1~}$} este minim posibila. Daca si in acest caz exista mai multe solutii, se va afisa cea in care {$l{~2~}$} este minim posibila. Daca si in acest caz este mai multe solutii, se va afisa cea in care suma celor patru numere este minim posibila.

h2. Restrictii

... ≤ ...

* {$3 ≤ N ≤ 512$}
* Fiecare element din matrice nu depaseste $10$ milioane
* Cele noua sume nu sunt in mod obligatoriu diferite doua cate doua
* Se garanteaza existenta cel putin a unei solutii

h2. Exemplu
table(example). |_. zone.in |_. zone.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|5
28 3 5 2 20 7 5 11 15
1 2 5 6 1
5 6 1 3 3
9 8 1 4 5
8 5 2 1 6
1 6 3 2 2
|1 3 2 3|

h3. Explicatie

...

Matricea se va _taia_ in modul urmator:
 
!problema/zone?image002.jpg!

== include(page="template/taskfooter" task_id="zone") ==

1560