Fişierul intrare/ieşire:flori2.in, flori2.outSursăONI 2010 baraj gimnaziu
AutorFlorentina Ungureanu, Zoltan SzaboAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inflori2.outExplicaţ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.
 
Trebuie sa te autentifici pentru a trimite solutii. Click aici