Polish version    English version  
  About Olympic


 News
 About Olympic
Schedule
Problems
Stage II
Regulations
Stage I - results
Stage II - results
For contestants
Helpful resources
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: e
Autor: Tomasz Malesiński
E: Hetmany

dzień czwarty 9 sierpnia 2002
Plik źródłowy: e.??? (np. pas, c, cpp)
Plik wejściowy: e.in
Plik wyjściowy: e.out

Jak wiadomo hetman w szachach atakuje figury w ośmiu kierunkach (góra, dół, lewo, prawo i cztery kierunki ukośne) i nie może przeskakiwać przez zajęte pola, więc atakuje tylko pierwszą figurę w każdym kierunku. Dana jest szachownica, na której pewne pola są już zajęte przez inne figury. Należy tak poustawiać pewną liczbę hetmanów na wolnych polach, aby liczba par wzajemnie atakujących się hetmanów była największa. Bierzemy pod uwagę pary nieuporządkowane, tzn. pary różniące się tylko kolejnością uważamy za identyczne.

Zadanie

Napisz program, który:

  • wczyta z pliku e.in opis szachownicy i liczbę hetmanów,
  • obliczy maksymalną liczbę par wzajemnie atakujących się hetmanów,
  • zapisze wynik w pliku e.out.

Wejście

W pierwszym wierszu pliku e.in znajdują się cztery liczby całkowite pooddzielane pojedynczymi spacjami: w, h, n, m (3 <= w,h <= 7, 2 <= n <= wh-m, n <= 7, 0 <= m <= wh-2), oznaczające odpowiednio szerokość i wysokość szachownicy, liczbę hetmanów do ustawienia i liczbę zajętych pól. W następnych m wierszach są po dwie liczby całkowite xi i yi, 1 <= xi <= w, 1 <= yi <= h. Są to współrzędne (pozioma i pionowa) i-tego zajętego pola.

Wyjście

W pierwszym i jedynym wierszu pliku e.out powinna znaleźć się jedna liczba całkowita - maksymalna liczba par wzajemnie atakujących się hetmanów.

Przykład

Dla pliku wejściowego e.in:

4 5 5 2
2 2
2 5

poprawną odpowiedzią jest plik wyjściowy e.out:

8



Print friendly version