Szachownica
Limit pamięci: 32 MB
Dana jest szachownica o rozmiarach , gdzie
jest nieparzystą liczbą całkowitą spełniającą nierówność , oraz zestaw kostek. Każda kostka ma kształt
prostokąta pokrywającego dokładnie dwa pola. Pola szachownicy są ponumerowane
kolejno wierszami - pola w pierwszym wierszu (od lewej do prawej) liczbami od
do , pola w drugim wierszu od do
i tak dalej aż do pola w prawym dolnym rogu, które ma numer
.
Z szachownicy wycinamy trzy dowolne pola, a następnie chcemy ją pokryć
kostkami, w taki sposób, aby każde nie wycięte pole pokrywała jedna kostka
(pokrywająca też jedno z sąsiednich pól), a pola wycięte pozostały nie pokryte.
Czy zawsze jest to możliwe?
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia rozmiar szachownicy oraz
trzy numery wyciętych pól szachownicy,
- bada, czy taką szachownicę można pokryć kostkami i jeśli nie, to zapisuje w
standardowym wyjściu odpowiedź NIE, a jeśli tak, to zapisuje w
standardowym wyjściu ciąg par liczb całkowitych
wskazujących ułożenie kostek pokrywające daną szachownicę.
Jeśli istnieje wiele sposobów pokrycia szachownicy kostkami, Twój program
powinien wypisywać tylko jeden z nich.
Wejście
W jedynym wierszu standardowego wejścia są zapisane cztery liczby pooddzielane
pojedynczymi odstępami. Pierwsza liczba to rozmiar szachownicy , a
trzy następne to numery wyciętych pól. Po ostatniej liczbie następuje koniec
wiersza.
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego
sprawdzać.
Wyjście
Standardowe wyjście powinno zawierać albo jedno słowo NIE, albo w
każdym z kolejnych wierszy dwie liczby oddzielone odstępem, to
znaczy numery dwóch sąsiednich pól pokrywanych przez jedną kostkę.
Przykłady
Dla danych wejściowych:
7 17 25 40
poprawną odpowiedzią jest:
18 19
20 21
8 9
10 11
12 13
14 7
6 5
4 3
1 2
15 22
16 23
29 36
30 37
24 31
32 39
43 44
38 45
46 47
48 49
41 42
33 34
35 28
26 27
Dla danych wejściowych:
7 25 32 40
poprawną odpowiedzią jest:
NIE
Autor zadania: Wojciech Rytter.