== include(page="template/taskheader" task_id="ferma3") ==
Poveste şi cerinţă...
Un fermier deţine o fermă de formă dreptunghiulară cu lungimea m metri şi lăţimea $n$ metri. Respectând principiul rotaţiei culturilor, fermierul şi‑a realizat un plan pentru semănarea culturilor în noul an. Astfel ,el a desenat un dreptunghi pe care l-a împărţit în $m * n$ celule, fiecare corespunzând unui metru pătrat, şi a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparţin aceleiaşi parcele dacă au aceeaşi culoare (sunt însămânţate cu aceeaşi cultură). Fermierul are posibilitatea să irige o sigură parcelă şi doreşte să aleagă parcela cu cea mai mare suprafaţă. Nefiind mulţumit de suprafaţa rezultată, s-a întrebat dacă ar putea schimba cultura de pe o singură celulă, astfel încât să obţină o parcelă de suprafaţă mai mare.
!problema/ferma3?f1.jpg!
h2. Cerinta
Dându-se dimensiunile fermei şi pentru fiecare celulă culoarea corespunzătoare culturii semănate, determinaţi:
Varianta $1$: Suprafaţa maximă a unei parcele în planul iniţial.
Varianta $2$: Numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură şi culoarea corespunzătoare noii culturi în vederea obţinerii celei mai mari parcele posibile.
h2. Date de intrare
Fişierul de intrare $ferma3.in$ ...
Fişierul de intrare $ferma3.in$ va conţine: Pe prima linie un număr natural $v$ $(1 ≤ v ≤ 2)$ indicând varianta cerinţei de rezolvare. Pe a doua linie două numere naturale $m$ şi $n$ separate printr-un spaţiu, cu semnificaţia din enunţ. Pe fiecare dintre următoarele $m$ linii se găsesc câte $n$ caractere (litere mici), reprezentând codurile culturilor ce vor fi semănate pe cele n celule corespunzătoare fiecărei linii.
h2. Date de ieşire
În fişierul de ieşire $ferma3.out$ ...
Fişierul de ieşire $ferma.out$ va conţine:
Varianta $1$ – pentru $v=1$: pe prima linie numărul natural $s$, reprezentând suprafaţa maximă a unei parcele.
Varianta $2$ – pentru $v=2$: pe prima linie două numere naturale separate printr-un spaţiu, reprezentând numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură, în vederea obţinerii unei parcele cu suprafaţa maximă;
pe a doua linie un caracter reprezentând codul culorii corespunzătoare noii culturi din celula determinată.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ m ≤ 400$
* $2 ≤ n ≤ 400$
* Numărul de culturi distincte este cel puţin $2$ şi cel mult $26$.
* $30%$ din teste vor avea pe prima linie valoarea $1$, iar restul de $70%$ din teste vor avea pe prima linie valoarea $2$.
* Pentru varianta $2$ se punctează orice soluţie care conduce la obţinerea unei parcele cu suprafaţa maximă. Nu se acordă punctaje parţiale.
h2. Exemplu
table(example). |_. ferma3.in |_. ferma3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag
| 11
|
h3. Explicaţie
...
!problema/ferma3?f2.jpg!
Datele corespund imaginilor de mai sus. Numerotarea parcelelor din imaginea $2$ este utilizată pentru a simplifica explicaţiile de mai jos şi nu influenţează datele problemei şi nici algoritmul de rezolvare.În varianta $1$ se determină şi se afişează suprafaţa maximă a unei parcele, care este egală cu $11$ şi corespunde parcelei $6$, de culoare verde (codificată cu litera $v$ în imaginea $1$ şi în fişierul de intrare).
== include(page="template/taskfooter" task_id="ferma3") ==
