Polish version    English version  
  Obozy Olimpiady


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
III obóz 2002
IV obóz 2003
V obóz 2004
VI obóz 2005
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Obóz im. A. Kreczmara 2002

Zadanie: ten

Tenis

dzień trzeci 8 sierpnia 2002
Plik źródłowy: ten.??? (np. pas, c, cpp)
Plik wejściowy: ten.in
Plik wyjściowy: ten.out

W tym roku w Bajtocji po raz pierwszy odbędzie się turniej tenisowy Bajtocja Open. Smok Bajtazar ma zamiar postawić pieniądze na niektórych zawodników. Zna ich wszystkich bardzo dobrze. Dla każdych dwóch zawodników Bajtazar wie na pewno, który z nich wygra, jeśli zagrają przeciwko sobie. Nie zna jedynie początkowego rozstawienia, które zostanie wylosowane tuż przed pierwszym meczem.

Turniej rozgrywany jest systemem pucharowym. W każdej rundzie każdy zawodnik pozostający jeszcze w turnieju rozgrywa jeden mecz. W każdym meczu przegrywający odpada z turnieju. Zawodnik, który pozostanie w turnieju jako jedyny, wygrywa.

Zadanie

Twoim zadaniem jest pomóc Bajtazarowi w ustaleniu, którzy zawodnicy mają szansę wygrać turniej. Napisz program, który:

  • wczyta informacje posiadane przez Bajtazara: liczbę zawodników oraz kto z kim jest w stanie wygrać,
  • wyznaczy listę zawodników, którzy mają jakąkolwiek szansę wygrać turniej,
  • zapisze wynik.

Wejście

W pierwszym wierszu pliku wejściowego ten.in znajduje się liczba zawodników N, N należy do zbioru {2,4,8,16}. Zawodnicy ponumerowani są od 1 do N. W każdym z kolejnych N wierszy znajduje się N liczb oddzielonych pojedynczymi odstępami. j-ta liczba w (i+1)-szym wierszu jest równa 1, gdy i <> j i zawodnik numer i pokonuje zawodnika numer j, a 0 w przeciwnym przypadku.

Wyjście

W jedynym wierszu pliku wyjściowego ten.out powinna znaleźć się oddzielona spacjami, posortowana rosnąco lista numerów zawodników, którzy mogą wygrać turniej.

Przykład

Dla pliku wejściowego ten.in:

4
0 0 1 1
1 0 1 0
0 0 0 1
0 1 0 0

poprawną odpowiedzią jest jest plik wyjściowy ten.out:

1 2



Wersja do druku