Polish version    English version  
  Olympic camps


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
III camp 2002
IV camp 2003
V camp 2005
VI camp 2005
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

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



Print friendly version