Prosba o algorytm

/*Bez polskich znakow jezeli nalezy ich uzywac byl bym wdzieczny za za
przeslanie mi uwagi na priva*/

    Dobra teraz na temat mam zadanie na olimpiade informatyczna tylko nie
rozumiem jednego algorytmu albo w nim jest blad jezeli ktos by mogl mi pomoc
bylo by wspaniale a oto zadanie:

/*Poczatek*/
    Na okregu stoi n osob ponumerowanych kolejno liczbami 0d 1 do n.Osoby te
tocza n-1 pojedynkow.W pierwszej rundzie jedna z tych osob.powiedzmy o
numerze i-toczy pojedynek z sasiadem z prawej,tzn.z osoba o numerze i++(lub
jesli i=n to z osoba o numerze n).Przegrany odpada z gry a sasiadem
zwyciezcy staje sie nastepna w kolejnosci osoba.Dana jest tez tabela
mozliwych wynikow pojedynkow w postaci macierzy(to wiem jak zrobic) A.Jesli
A[i][j]==1,to osoba o numerze i zawsze wygywa z osoba o numerze j.Jezeli
a[i][j]==0 to osoba o numerze i przegrywa zosoba o numerze j. Mowimy ze
osoba k moze wygrac zawody jezeli istnieje taki ciag n-1 losowan, w wyniku
ktorego bedzie ona zwyciezca ostatniego pojedynku.
Napisz program ktory
a)wczyta z pliku txt MUS.IN Macierz A(banal)
b)wyznaczy numery osob ktore moga wygrac zawody(hhhh :((((( )
c)zapisze je do pliku txt MUS.OUT ( :)cool )

A oto przykala w ktorym wedlug mnie jest blad( ale raczej napewno sie myle)
Wejscie:
W pierwszym wierszu pliku txt MUS.IN dana jest liczba calkowita n
spelniajaca nierownosc 3 < n <=100 w kazdym nastepnym n wierszy znajduje sie
jedno slowo zlozone z n znakow  '0' || '1'.Znak stojacy na j-tym miejscuw
i-tym z tych wierszy oznacza wartosc A[i][j].Oczywiscie
A[i][j]=1-A[j][i],dla i != j a[i][i]=1
Wyjscie W pierwszym wierszu pliku txt MUS.OUT nalezy zapisac liczbe m tych
osob jtore moga wygrac zawody.W nastepnych m wierszach nalezy zapisac numery
tych osob w kolejnosci rosnacej,po jednym numerze w lini

Przyklad
/*MUS.IN*/
7
1111101
0101100
0111111
0001101
0000101
1101111
0100001
/*End mus.ini*/

Kolejnosc pojedynkow ( nie rozumiem kolejnosci wyznaczania tych pojedynkow)
1-2,1-3,5-6,7-1,4-6,6-1 daje ostateczna wygrna osobe o numerze 6.

/*MUS.OUT*/
3
1
3
6

koniec przykladu
W tym wszystkim nie jarze kolejnosci wyznaczania tych pojedynkow blagam o
pomoc

ns88

Thanks

...

Problem ktory opisales, nie polega na wyznaczeniu potencjalnych pojedynkow, ale
tylko znalezieniu mozliwych zwyciescow. Sadze, ze mozna rozwiazac to tak (dane
jak z przykladu). Rozwazam wszystkie mozliwe pojedynki w kazdej turze, przyklad
wszystko wyjasni:
1 2 3 4 5 6 7, 1
 \/ \/ \/ \/ \/ \/ \/
 1 3 3 4 6 6 1, 1 (zwyciescy)
  \/    \/ \/     \/
  1    3 6     6, 1  (zwyciescy)
     \/  \/         \/
     1  3         6, 1 (zwyciescy)
       \/    \/       \/
       1     3       6

Objasnienia do rysunku: \/ - pojedynek; po przecinku jest umieszczony pierwszy
zawodnik z listy.
Jak widac orzymalem wynik zgodny z oczekiwanym wyjsciem. Mozna latwo odtworzyc
jeden z mozliwych schematow gry, aby wygrala 6 i chyba sie zgadza z podanym.
Takich schematow moze byc wiecej niz jeden. Algorytm zatrzymuje sie, kiedy nie
ulega zmianie zbior zwyciescow. Nad implementacja sie nie zastanawialem, ale
jakies dwa wektory indeksow zwyciescow (dwa, zeby sprawdzic warunek zatrzymania)
troche petli i ifow, nie jest to takie trudne.

Z powazaniem Sebastian Lisek

serio? ja tez robie te zadania... :)

Tez sie zastanawialem nad tym, ale nic nie wymyslilem. Wedlug mnie powinno
byc cos w stylu: 1-2 1-3 3-4 3-5 5-6 ...... (wyniki walk zmyslone).

Ale mimo tego rozwiazalem to zadanie. Jesli cie to wogole interesuje to
powiem ze wedlug mnie jest to najlatwiejsze z tych czterech zadan...

Borlot / Majorca Team (MCT)
Tomasz Nedza

odp. obiektywna: jak uwazasz
odp. tendencyjna: nie nalezy. cholery dostaje jak slysze slowa 'jezyk
polski'. (jak bede mial 3 na koniec to bedzie to spory moj sukces)

Co do zadanka - nie mam juz nic do dodania, otrzymales wyczerpujace
odpowiedzi.
Jest ono rzeczywiscie najprostsze z tych czterech.
Najgorsze jest chyba - monocyfrowe reprezentacje.

Pozdrawiam

Adam Michalski

potencjalnych pojedynkow, ale


rozwiazac to tak (dane


kazdej turze, przyklad


umieszczony pierwszy


Mozna latwo odtworzyc


zatrzymuje sie, kiedy nie


warunek zatrzymania)

W oryginalnej tresci zadania jest jedno wymaganie (plik
wyjsciowy musi byc posortowany
rosnaco), które naprowadzilo mnie na takie rozwiazanie:

Po kolei dla kazdego zawodnika i (i=1..n) sprawdzamy, czy
moze on wygrac. Ale sprawdzenie
to robimy "od tylu", starajac sie dobrac serie pojedynków
n-1, n-2, n-3, ... 1 w wyniku
której  i-ty zawodnik wygrywa (tzn. dla pojedynku n-1
poszukujemu dla i-tego slabszego
przeciwnika, bo ostatni pojedynek musi byc na pewno wygrany
przez i-tego. Nastepnie
poszukujemy jakiegos pojedynku n-2, (albo i-ty rabie
jakiegos slabeusza albo przeciwnik dla i-tego
rabie jakiegos innego i wchodzi do finalu z i-tym), i tak
dale)j.

Takie przeszukiwanie da sie pewnie w miare ladnie zapisac
rekurencja - wyglada to na
przeszukiwanie z nawrotami (bo nie kazdy "odwrotny" ciag
pojedynków doprowadzi nas
do sytuacji wyjsciowej; jesli zaden, to znaczy ze i-ty nie
moze wygrac).

Mam nadzieje, ze za bardzo nie naklamalem ...
Pozdrowienia.
J.K.

(dane

Myslisz, ze tak mozna. Bo ja bym glowy nie dal. Przynajmniej nie wydaje mi
sie to oczywiste. I na razie nie znajduje na to sensowngo dowodu.

Pozdrawiam,
    Michal