Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 70 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5, 6, 7  Następna strona
Mistrzostwa - testy 
Autor Wiadomość
Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 14:15
Posty: 106
Post Re: Mistrzostwa - testy
Potwierdzam wszystkie testy z wszystkich zadań. Szkoda tylko że nie potrafię wstać o 6. Mimo wszystko życzę wygranej :)


14 paź 2010, o 22:44
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 23:31
Posty: 30
Post Re: Mistrzostwa - testy
Sebastian Daniel Nowak napisał(a):
Również je potwierdzam. No i standardowo paczka ode mnie:
http://www.speedyshare.com/files/24688856/mis_tests.rar
Wejście jest na pewno zgodne z treścią zadania, nie ma żadnych cykli i nikt nie jest swoim przełożonym.


Potwierdzam ;)


14 paź 2010, o 22:59
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 13:38
Posty: 43
Post Re: Mistrzostwa - testy
a mógłby ktoś dać te tesy spakowane np w rar ?? Bo nie wiem jakim programem to otworzyć :)


15 paź 2010, o 08:39
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 25 paź 2009, o 12:35
Posty: 37
Post Re: Mistrzostwa - testy
Norbert Gregorek napisał(a):
a mógłby ktoś dać te tesy spakowane np w rar ?? Bo nie wiem jakim programem to otworzyć :)


Nie!

Jak możesz!

Rar jest ZZUUYY!

//Jak już musisz pod windowsem to 7zip.


15 paź 2010, o 14:53
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Mistrzostwa - testy
To jak robiliście to zadanie moi mili?
Ono chyba było najtrudniejsze z tej rundy.

Ja sobie zrobiłem dodatkowy wierzchołek -1, aby ten graf był spójny. No i puszczam sobie DFS od tego wierzchołka. I to trochę taki dynamik. Rozwiązujemy dla liści, dla większego poddrzewa, mając to to rozwiążemy dla większego i tak dalej. Każde poddrzewo (każdy syn) zwraca ojcu dwie liczby. Ile par się udało utworzyć i ile niesparowanych zostało. No i ojciec otrzymuje od synów te wartości i kombinuje z nimi. Jakąś parę z jednego poddrzewa można zniszczyć by 2 powstałe wierzchołki sparować z niesparowanymi dwoma z innego poddrzewa. :)


15 paź 2010, o 18:36
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 25 paź 2009, o 12:35
Posty: 37
Post Re: Mistrzostwa - testy
Adam Nieżurawski napisał(a):
To jak robiliście to zadanie moi mili?
Ono chyba było najtrudniejsze z tej rundy.

Ja sobie zrobiłem dodatkowy wierzchołek -1, aby ten graf był spójny. No i puszczam sobie DFS od tego wierzchołka. I to trochę taki dynamik. Rozwiązujemy dla liści, dla większego poddrzewa, mając to to rozwiążemy dla większego i tak dalej. Każde poddrzewo (każdy syn) zwraca ojcu dwie liczby. Ile par się udało utworzyć i ile niesparowanych zostało. No i ojciec otrzymuje od synów te wartości i kombinuje z nimi. Jakąś parę z jednego poddrzewa można zniszczyć by 2 powstałe wierzchołki sparować z niesparowanymi dwoma z innego poddrzewa. :)


Strasznie skomplikowane.
Ja zawsze łączyłem 2 korzenie o największej ilości synów (drugim kryterium był rozmiar poddrzewa). Jak nie było dwóch korzeni - to wywalałem ten korzeń, który był.


15 paź 2010, o 18:47
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post Re: Mistrzostwa - testy
Ja trzymałem na kolejce priorytetowej najbardziej oddalone liście i usuwałem parami, ale to O(nlogn), więc 10pkt się nie spodziewam.


15 paź 2010, o 18:49
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 14:15
Posty: 106
Post Re: Mistrzostwa - testy
Kopiec binarny zawierający wszystkie liście w lecie, pełniący rolę kolejki priorytetowej o własności głębokości liści w drzewach.

Kod:
answer = 0
Dopóki myHeapSize > 2:
    answer = answer + 1
    a = extract()
    b = extract()
    dodanie do kopca ojców a i b jeśli są nowymi liśćmi


15 paź 2010, o 18:52
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Mistrzostwa - testy
Ja to robiłem tak jak Adam, wg mnie to dość proste rozwiązanie. Ale mimo tego, że to liniówka, to trochę się boję, bo na moim kompie działało dość wolno (najpierw rekurencyjny DFS do obliczenia ile każdy wierzchołek ma przodków, a potem inna rekurencyjna funkcja odpowiadająca za obliczenia tego wszystkiego od liści i pchanie informacji w górę).


15 paź 2010, o 19:03
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Mistrzostwa - testy
Łasica, a na kija ci była wiedza ile kto ma przodków?


15 paź 2010, o 19:07
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 70 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5, 6, 7  Następna strona


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL