banana

Banana

== include(page="template/taskheader" task_id="banana") ==

==Include(page="template/taskheader" task_id="banana")==

Poveste ...

==Include(page="template/raw")==
 
Se considera o padure tropicala, reprezentata sub forma unui caroiaj dreptunghiular. Celula din coltul stanga sus al caroiajului are coordonatele $(1, 1)$, iar coordonatele celorlalte celule sunt determinate de linia si coloana pe care se afla. In anumite celule ale caroiajului sunt plasati bananieri; o celula contine cel mult un bananier. Mai multi bananieri care se invecineaza pe orizontala sau verticala formeaza o zona de bananieri. Intr-o astfel de zona, CEKILI se deplaseaza usor, cu agilitatea-i cunoscuta, de la un bananier la altul.
 
Maimuta CEKILI este lacoma si nu ii ajung bananele dintr-o singura zona. Tarzan vrea sa-si ajute prietena. Pentru aceasta, el ar putea conecta exact $K$ zone de bananieri innodand mai multe liane si astfel CEKILI s-ar putea deplasa de la o zona la alta utilizand lianele. Evident, Tarzan trebuie sa aleaga zonele astfel incat numarul total de bananieri din cele $K$ zone sa fie maxim.

h2. Cerinta

...

Determinati numarul maxim de bananieri care se poate obtine prin conectarea a exact $K$ zone.

h2. Restrictii

h2. Date de Intrare
 
Fisierul de intrare $banana.in$ contine:
 
 
 
banana.in ]Semnificatie
Nr K Nr - numarul de bananieri
 
x[1] y[1 K - numarul de zone ce pot fi conectate
 
]x[2] y[2 x[i] - linia pe care se afla bananierul i

...

]... y[i] - coloana pe care se afla bananierul i

h2. Date de intrare

x[Nr] y[Nr

...

h2. Date de Iesire

h2. Date de iesire

Fisierul de iesire banana.out va contine pe prima linie numarul maxim de bananieri care se poate obtine prin conectarea zonelor.

...

h2. Restrictii
 
Ÿ 1 -L- Nr -L- 16 000
 
Ÿ 1 -L- xi, yi -L- 10 000, "iI{1,2,...,Nr}
 
Ÿ in testele utilizate K nu va depasi numarul de zone.
 
Ÿ doua pozitii se invecineaza pe orizontala daca sunt pe aceeasi linie si pe coloane consecutive, respectiv pe verticala daca sunt pe aceeasi coloana si pe linii consecutive.

h2. Exemplu

| banana.in | banana.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="banana") ==
 

|banana.in |banana.out |
 
|10 3 |9 |
| | |
|7 10 | |
| | |
|1 1 | |
| | |
|101 1 | |
| | |
|2 2 | |
| | |
|102 1 | |
| | |
|7 11 | |
| | |
|200 202 | |
| | |
|2 1 | |
| | |
|3 2 | |
| | |
|103 1 | |
| | |
| | |
 
 
 
==Include(page="template/taskfooter" task_id="banana")==