W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Dana jest szachownica o wymiarach , z której usunięto pewną liczbę pól. Należy wyznaczyć maksymalną liczbę skoczków (koników) szachowych, które można ustawić na pozostałych polach szachownicy tak, żeby żadne dwa skoczki nie atakowały się nawzajem.
Napisz program, który:
W pierwszym wierszu znajdują się dwie liczby całkowite i , gdzie , . Liczba oznacza rozmiar szachownicy, a oznacza liczbę usuniętych pól.
W każdym z kolejnych wierszy jest zapisana para liczb naturalnych i , gdzie , oddzielonych pojedynczym odstępem. Są to współrzędne usuniętych pól. Lewy górny róg szachownicy ma współrzędne , natomiast prawy dolny róg ma współrzędne . Pola nie powtarzają się.
Na standardowym wyjściu należy zapisać dokładnie jeden wiersz, zawierający pojedynczą liczbę całkowitą równą maksymalnej liczbie wzajemnie nie atakujących się skoczków, które można ustawić na zadanej szachownicy.
Dla danych wejściowych:
3 2 1 1 3 3
poprawną odpowiedzią jest:
5