==Include(page="template/taskheader" task_id="banana")==
== include(page="template/taskheader" task_id="banana") ==
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.
Poveste ...
h2. Cerinta
Determinati numarul maxim de bananieri care se poate obtine prin conectarea a exact $K$ zone.
h2. Date de intrare
...
Fisierul de intrare $banana.in$ contine:
h2. Restrictii
table(example). | Nr K
x{~1~} y{~1~}
x{~2~} y{~2~}
...
x{~Nr~} y{~Nr~}
| Nr - numarul de bananieri
K - numarul de zone ce pot fi conectate
x{~i~} - linia pe care se afla bananierul i
y{~i~} - coloana pe care se afla bananierul i |
h2. Date de iesire
h2. Date de intrare
Fisierul de iesire $banana.out$ va contine pe prima linie numarul maxim de bananieri care se poate obtine prin conectarea zonelor.
...
h2. Restrictii
h2. Date de iesire
* $1 ≤ Nr ≤ 16 000$
* $1 ≤ x{~i~}, y{~i~} ≤ 10 000, i ∈ {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
table(example). |_. banana.in |_. banana.out |
| 10 3
7 10
1 1
101 1
2 2
102 1
7 11
200 202
2 1
3 2
103 1
| 9 |
| banana.in | banana.out |
| linia1
linia2
linia3
| linia1
linia2
|
==Include(page="template/taskfooter" task_id="banana")==
== include(page="template/taskfooter" task_id="banana") ==
