== include(page="template/taskheader" task_id="flori2") ==
Poveste și cerință...
!>problema/flori2?flori2-1.gif!
Pentru primăvara următoare, firma care răspunde de amenajarea spațiului verde din centrul orașului Slatina și-a propus să planteze rânduri de flori dispuse diagonal, formate din parcele având fiecare un anumit număr de flori. Irigarea florilor se realizează cu o pompă care se deplasează în jurul spațiului verde, începând din colțul din dreapta sus, mergând în sens invers acelor de ceasornic. Rândurile sunt numerotate cu 1, 2, 3, ... începând din colțul din dreapta sus, respectând sensul de deplasare al pompei. La udarea unui rând de flori se pompează un număr de litri de apă egal cu numărul de flori de pe rândul respectiv.
Debitul apei la sistemul de pompare se poate păstra, poate fi mărit, dar nu poate fi micșorat. Un rând de flori poate fi udat numai dacă are un număr de flori mai mare sau egal cu cel al ultimului rând udat, cu excepția primului rând ales pentru a fi udat. Orice rând de flori poate fi udat cel mult o dată, la oricare din capetele sale. Apa se oprește la revenirea în colțul de plecare.
h2. Cerință
Fiind dată o matrice cu n linii și m coloane, în care fiecare element reprezintă numărul de flori dintr-o parcelă, să se determine numărul maxim de flori ce pot fi udate printr-o rotire completă a pompei în jurul spațiului verde, iar dintre soluțiile determinate, pe cea având număr minim de rânduri cu flori, precum și numerele de ordine ale rândurilor udate, respectând ordinea în care au fost udate.
h2. Date de intrare
Fișierul de intrare $flori2.in$ ...
Fișierul de intrare $flori2.in$ conține pe prima linie numerele naturale *n* și *m* reprezentând numărul de linii, respectiv numărul de coloane ale matricei; fiecare din următoarele *n* linii conține câte *m* numere naturale nenule, separate prin câte un spațiu, reprezentând numărul de flori din fiecare parcelă de pe linia respectivă a matricei.
h2. Date de ieșire
În fișierul de ieșire $flori2.out$ ...
Fișierul de ieșire $flori2.out$ va conține:
* pe prima linie numărul maxim de flori ce pot fi udate;
* pe a doua linie numărul minim de rânduri udate;
* pe a treia linie numerele de ordine ale rândurilor stropite, în ordinea udării lor, separate prin câte un spațiu.
h2. Restricții
* $... ≤ ... ≤ ...$
* $0 < n, m ≤ 900$
* $0 < numărul de flori dintr-o parcelă ≤ 60000$
* Pentru prima cerință rezolvată corect se obține 40% din punctaj, pentru primele două cerințe rezolvate corect se obține 60% din punctaj.
h2. Exemplu
table(example).
|_. flori2.in |_. flori2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. flori2.in |_. flori2.out |_. Explicație |
| 5 6
2 1 3 5 2 3
3 4 5 6 4 3
2 3 6 3 4 9
1 2 7 2 5 1
10 5 14 10 10 3
| 104
7
1 2 4 5 8 7 6
| La deplasarea pe prima latură orizontală a stratului de flori sunt
udate rândurile 1, 2, 4 și 5, la deplasarea pe prima latură
verticală se udă rândul 8, iar rândurile 7 și 6 la deplasarea pe
latura de jos a stratului.
!problema/flori2?flori2-2.gif!
|
== include(page="template/taskfooter" task_id="flori2") ==
