| O olimpiadzie -> Zadania -> III OI 1995/1996 |  |
|
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: (ai, bi), ( ci, di), gdzie (ai, bi) to współrzędne pola w lewym górnym rogu prostokąta (wiersz, kolumna), zaś (ci, di) to współrzędne pola w prawym dolnym rogu, 1 <= ai <= ci <= n oraz 1 <= bi <= di <= 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