Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-12 17:06:40.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:banana.in, banana.outSursăONI 2002
AutorMihai Patrascu, Roxana TamplaruAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Cerinta

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

Date de intrare

Fisierul de intrare banana.in contine:

Nr K
x1 y1
x2 y2
...
xNr yNr
Nr - numarul de bananieri
K  - numarul de zone ce pot fi conectate
xi - linia pe care se afla bananierul i
yi - coloana pe care se afla bananierul i

Date de iesire

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

Restrictii

  • 1 ≤ Nr ≤ 16 000
  • 1 ≤ xi, yi ≤ 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

Exemplu

banana.inbanana.out
10 3
7 10
1 1
101 1
2 2
102 1
7 11
200 202
2 1
3 2
103 1
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?