Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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




Wersja do druku