|
|||||||||||||||
|
Muszkieterowie
W czasach Ludwika XIII i jego potężnego ministra, kardynała Richelieu, w gospodzie pod Pełnym Antałkiem raczyło się jadłem i winem n muszkieterów. Wina było pod dostatkiem, a że muszkieterowie byli skorzy do zwady, doszło do wielkiej awantury, w której każdy muszkieter obraził wszystkich pozostałych. Musiało dojść do pojedynków, ale kto miał się z kim pojedynkować i w jakiej kolejności? Uzgodnili (po raz pierwszy od awantury zrobili coś zgodnie), że staną na okręgu w ustalonej kolejności i będą ciągnąć losy. Wylosowany muszkieter toczył pojedynek ze swoim sąsiadem z prawej. Przegrany "odpadał z gry", a dokładniej - służący wynosili jego zwłoki. Sąsiadem wygrywającego stawał się następny muszkieter, stojący za przegranym. Po latach, gdy historycy czytali wspomnienia zwycięzcy, spostrzegli, że ostateczny wynik zależał w istotny sposób od kolejności wylosowanych pojedynków. Zauważyli bowiem, że dotychczasowe treningi fechtunku pokazywały, kto z kim mógł wygrać pojedynek. Okazało się, że - mówiąc językiem matematycznym - relacja "A wygrywa z B" nie była przechodnia! Mogło się zdarzyć, że muszkieter A walczył lepiej od muszkietera B, B lepiej od C, a C lepiej od A. Oczywiście wśród takiej trójki wybór pierwszego pojedynku decydował o ostatecznym wyniku! Jeśli pierwsi będą walczyć A i B, to ostatecznie wygra C, ale jeśli pierwszymi będą B i C, to ostatecznie wygra A. Historycy, zafascynowani tym odkryciem, postanowili sprawdzić, którzy muszkieterowie mogli przeżyć - od tego zależał przecież los Francji, a wraz z jej losem, los całej cywilizowanej Europy! Zadanie
Na okręgu stoi n osób, ponumerowanych kolejno liczbami od 1 do n. Osoby te toczą
n-1 pojedynków. W pierwszej rundzie jedna z tych osób powiedzmy o numerze i -
toczy pojedynek z sąsiadem z prawej, tzn. osobą o numerze i+1 (lub, jeśli i=n, to z osobą o numerze 1). Przegrany odpada z gry, sąsiadem zwycięzcy
staje się następna w kolejności osoba. Dana jest też tabela możliwych wyników pojedynków
w postaci macierzy A. Jeśli Ai,j=1, to osoba o numerze i
zawsze wygrywa z osobą o numerze j. Jeżeli Ai,j=0, to osoba o numerze
i przegrywa z osobą o numerze j. Mówimy, że osoba k może wygrać
zawody, jeżeli istnieje taki ciąg n-1 losowań, w wyniku którego będzie ona zwycięzcą
ostatniego pojedynku.
WejścieW pierwszym wierszu pliku testowego MUS.IN dana jest liczba całkowita n spełniająca nierówność 3 <= n <= 100. W każdym z następnych n wierszy znajduje się jedno słowo złożone z n znaków 0 lub 1. Znak stojący na j-tym miejscu w i-tym z tych wierszy oznacza wartość Ai,j (tzn. jeśli tym znakiem jest jedynka, to Ai,j=1, a jeśli zero, to Ai,j=0). Oczywiście Ai,j=1-Aj,i, dla i<>j. Przyjmujemy, że Ai,i=1, dla każdego i. WyjścieW pierwszym wierszu pliku wyjściowego MUS.OUT należy zapisać liczbę m tych osób, które mogą wygrać zawody. W następnych m wierszach należy zapisać numery tych osób w kolejności rosnącej, po jednym numerze w wierszu. PrzykładDla pliku wejściowego MUS.IN
7 1111101 0101100 0111111 0001101 0000101 1101111 0100001 kolejność pojedynków: 1-2, 1-3, 5-6, 7-1, 4-6, 6-1 daje ostateczną wygraną osobie o numerze 6. Można też sprawdzić, że jeszcze tylko osoby o numerach 1 i 3 mogą wygrać zawody. Zatem plik wyjściowy MUS.OUT powinien wyglądać następująco: 3 1 3 6 Twój program powinien szukać pliku MUS.IN w katalogu bieżącym i tworzyć plik MUS.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę MUS.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku MUS.EXE |