Fişierul intrare/ieşire:zone.in, zone.outSursăpreONI 2007, Runda 2
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Zone

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 l1 si l2 si doua coloane c1 si c2, 1 ≤ l1 < l2 < N, 1 ≤ c1 < c2 < N si se taie matricea de-alungul acestor linii, respectiv coloane, ca in figura de mai jos:

            

Se observa ca zonele 1, 4 si 7 sunt formate din toate elementele de pe primele c1 coloane, zonele 2, 5 si 8 sunt cuprinse intre coloanele c1+1 si c2, iar zonele 3, 6, 9 sunt intre coloanele c2+1 si N. Similar, zonele 1, 2 si 3 sunt intre liniile 1 si l1, 4, 5 si 6 intre l1+1 si l2, iar zonele 7, 8 si 9 intre liniile l2+1 si N. Se noteaza intr-o ordine oarecare sumele elementelor pentru fiecare regiune din cele noua astfel formate.
Sa se determine liniile l1 si l2 si coloanele c1 si c2 astfel incat sa se formeze cele noua sume date.

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.

Date de iesire

Fisierul de iesire zone.out va contine o singura linie pe care se afla patru numere naturale, l1, l2, c1 si c2, despartite de exact un spatiu, reprezentand solutia problemei. Daca sunt mai multe solutii posibile se va afisa cea in care l1 este minim posibila. Daca si in acest caz exista mai multe solutii posibile, se va afisa cea in care c1 este minim posibila. Daca si in acest caz exista mai multe solutii, se va afisa cea in care l2 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.

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

Exemplu

zone.inzone.out
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

Explicatie

Matricea se va taia in modul urmator:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content