NézetNyomtat

Kert
Címkék > Feladat

Kert

IOI 2005, 1. nap, 1. feladat: gar.pdf
Bájtember kertjében N rózsa van. Munkái miatt már nem tud elég időt szakítani a kertészkedésre, ezért szeretne felvenni két kertészt, akik a rózsák egy részét gondoznák. Úgy tervezi, hogy egy-egy téglalap alakú részt kerít el a kertészek számára úgy, hogy a területek diszjunktak, és mindegyikben pontosan K rózsa van. Mindezt úgy szeretné megtenni, hogy a felhasznált kerítés összhossza minimális legyen.

Bemenet

Az első sor a telek oszlopainak és sorainak számát adja meg (1 és 250 közötti méretek). A második sor N és K értékét (N legfeljebb 5000, K legfeljebb N fele). Utána a rózsák "koordinátái" következnek oszlop-sor sorrendben.

Kimenet

A minimális kerítéshossz, vagy "NO", ha a probléma nem oldható meg.

Példa

gar.ingar.out
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1
22

Tesztadatok