Fișierul intrare/ieșire	flori2.in, flori2.out	Sursă	ONI 2010 baraj gimnaziu
Autor	Florentina Ungureanu | Zoltan Szabo	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Flori2 (baraj gimnaziu)

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.

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.

Date de intrare

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.

Date de ieșire

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.

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.

Exemplu

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.