Olimpiada Informatyczna

III Olimpiada Informatyczna 1995/96

Zadanie: WIE

Autor: Krzysztof Diks

Wieże

Zawody II stopnia

Plik źródłowy:	`WIE.???` (np. `pas`, `c`, `cpp`)
Plik wykonywalny:	`WIE.exe`
Plik wejściowy:	`WIE.in`
Plik wyjściowy:	`WIE.out`

Na szachownicy n * n ustawiamy n wież, gdzie 1 <= n <= 3000. Ustawienie wież musi spełniać następujące warunki:

Dla każdego i = 1,...,n, i-tą wieżę wolno postawić tylko w prostokącie określonym przez dwie pary współrzędnych: (a_i, b_i), ( c_i, d_i), gdzie (a_i, b_i) to współrzędne pola w lewym górnym rogu prostokąta (wiersz, kolumna), zaś (c_i, d_i) to współrzędne pola w prawym dolnym rogu, 1 <= a_i <= c_i <= n oraz 1 <= b_i <= d_i <= n. Pole w lewym górnym rogu szachownicy ma współrzędne (1, 1), zaś pole w prawym dolnym rogu ma współrzędne (n, n).
Żadne dwie wieże nie mogą się atakować, to znaczy nie mogą stać w tym samym wierszu lub tej samej kolumnie.

Zadanie

Napisz program, który:

wczytuje z pliku tekstowego WIE.IN rozmiar szachownicy n oraz dla każdego i = 1, ..., n współrzędne prostokąta, w którym wolno postawić i-tą wieżę,
bada, czy można ustawić wieże, każdą w ustalonym dla niej prostokącie, tak aby żadne dwie nie atakowały się wzajemnie i jeśli tak, znajduje jedno takie ustawienie,
zapisuje w pliku tekstowym WIE.OUT jedno ustawienie wież spełniające warunki zadania albo jedno słowo NIE, jeśli takie ustawienie nie istnieje.

Wejście

W pierwszym wierszu pliku WIE.IN jest zapisana jedna liczba całkowita dodatnia n <= 3000. W każdym z n następnych wierszy są zapisane cztery liczby całkowite dodatnie nie większe niż n oddzielone pojedynczym odstępem. Liczby w i-tym z tych wierszy są współrzędnymi prostokąta, w którym wolno postawić i-tą wieżę.

Wyjście

W pliku WIE.OUT należy zapisać: jedno słowo NIE, albo w każdym z kolejnych n wierszy dwie liczby całkowite oddzielone pojedynczym odstępem. Liczby w i-tym wierszu powinny określać ustawienie i-tej wieży (wiersz kolumna); ta wieża powinna leżeć w prostokącie, którego współrzędne podano w (i + 1)-szym wierszu pliku WIE.IN. Zwróć uwagę, że pozycje wież powinny być wypisane w takiej kolejności, w jakiej zostały wczytane współrzędne prostokątów, w których te wieże mogą się znaleźć.

Przykład

Dla pliku WIE.IN:
4
1 1 1 1
1 3 2 4
3 1 4 2
2 2 4 4

jednym z poprawnych rozwiązań jest plik WIE.OUT:
1 1
2 3
3 2
4 4

Twój program powinien szukać pliku WIE.IN w katalogu bieżącym i tworzyć plik WIE.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę WIE.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku WIE.EXE