| Historia OI -> IV OI 1996/1997 -> Zadania |  |
|
IV Olimpiada Informatyczna 1996/97
|
|
Zadanie: LOT
|
Autor: Wojciech Guzicki
|
| Zawody II stopnia |
| Plik źródłowy: | LOT.??? (np. pas, c, cpp) |
| Plik wykonywalny: | LOT.exe |
| Plik wejściowy: | LOT.in |
| Plik wyjściowy: | LOT.out |
W państwie X istnieją lotniska w n miastach. Znane są maksymalne "przepustowości" tych lotnisk - lotnisko w mieście Mi może mieć co najwyżej di połączeń lotniczych z innymi miastami. Należy zaplanować sieć połączeń lotniczych między tymi miastami w taki sposób, by miasto Mi miało dokładnie di połączeń z innymi miastami, przy czym zakładamy, że każde połączenie jest dwukierunkowe i każde miasto może mieć z innym tylko jedno połączenie.
Zadanie
Napisz program, który:- wczytuje z pliku tekstowego LOT.IN liczbę n miast oraz liczby di,
- układa sieć połączeń lotniczych, taką że dla każdego i od 1 do n miasto Mi ma dokładnie di połączeń z innymi miastami,
- zapisuje w pliku LOT.OUT listę wszystkich tworzących sieć połączeń.
Wejście
W pierwszym wierszu pliku tekstowego LOT.IN jest zapisana liczba całkowita n spełniająca nierówność 3 <= n <= 500. Jest to liczba miast.W kolejnych n wierszach są zapisane liczby całkowite dodatnie di, po jednej w każdym wierszu.
Wyjście
W pliku tekstowym LOT.OUT należy zapisać wszystkie połączenia lotnicze sieci utworzonej przez Twój program. Każde połączenie należy zapisać w osobnym wierszu w postaci dwóch liczb całkowitych dodatnich oddzielonych pojedynczym odstępem, tj. numerów dwóch połączonych miast. Numery miast w wierszu mogą występować w dowolnej kolejności; również kolejność zapisywania połączeń w pliku jest dowolna.
Przykład
Dla pliku LOT.IN6 2 3 2 4 1 2przykładem poprawnego rozwiązania jest plik LOT.OUT
5 4 4 2 1 2 2 3 6 3 4 6 4 1
Twój program powinien szukać pliku LOT.IN w katalogu bieżącym i tworzyć plik LOT.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę LOT.???, 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 LOT.EXE.