Polish version    English version  
  OI books


 News
 About Olympic
 History of OI
 OI books
Publications in English
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2003/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
Where to buy?
Order
PS and PDF files
 National team
 Olympic camps
 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