Polish version    English version  
  Historia OI -> VI OI 1998/1999 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VI Olimpiada Informatyczna 1998/99

Zadanie: MUS
Autor: Wojciech Guzicki
Muszkieterowie

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

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.
Napisz program, który:

  • wczyta z pliku tekstowego MUS.IN macierz A
  • wyznaczy numery osób, które mogą wygrać zawody,
  • zapisze je do pliku tekstowego MUS.OUT.

Wejście

W 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ście

W 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ład

Dla 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




Wersja do druku