Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 2 ] 
[Runda 26] - Wyścigi Futerkowych Zaprzęgów 
Autor Wiadomość
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post [Runda 26] - Wyścigi Futerkowych Zaprzęgów
Czy ktoś mógłby opisać poprawne rozwiązanie? Z tego co widziałem, to nikt nie dostał za to zadanie 10 pts., jednak może ktoś ma poprawny algorytm, ale zrobił np. drobny błąd w implementacji? Jak nikt nie będzie wiedział jak to rozwiązać, to co wtedy? Jakieś wskazówki od autora? Podejrzewam, że to jakiś dynamik, bo zachłanny dostał 2x WA.


3 maja 2010, o 16:27
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 19 cze 2009, o 12:42
Posty: 54
Post Re: [Runda 26] - Wyścigi Futerkowych Zaprzęgów
Zapomniałam dopisać warunek na dwie kolejne pary... Już jest AC. Tak, to jest dynamik.
Załóżmy, że w pewien sposób wiemy jak rozłożone są rasy chomików w zaprzęgu i chcemy tylko dopasować dostępne chomiki tych ras. Wśród optymalnych rozwiązań jest to, w którym siły chomików od początku zaprzęgu są niemalejące. W takim razie posortuję sobie osobno obie rasy chomików i będę rozpatrywać tylko 2k najlepszych.
Rozpatrzę sobie takiego dynamika: stanem będzie (numer aktualnej pary, numer najsilniejszego nieużytego jeszcze chomika typu b, typ chomika w ostatniej parze po lewej, długość grupy chomików po lewej, typ chomika w ostatniej parze po prawej, długośc grupy chomików po prawej)
Zauważmy, że jeśli wiem ile było do tej pory par oraz ile było do tej pory chomików typu b, możemy łatwo w czasie stałym znaleźć liczbę chmoików typu c, więc nie musimy pamiętać tej liczby.
Przez długość grupy chomików rozumiemy długość najdłuższego łańcucha chomików tego samego typu kończącego się na ostatniej parze. Przykładowo dla zaprzęgu
Kod:

bbbccbcbbbcbbb
bccbcbbcbcbccb
 

Długości te to 3 oraz 1.
Stanów jest k * (2*k) * 2 * 3 * 2 * 3 czyli 72*10^4
Długość łańcucha nie może przekroczyć 3 bo tak mówi treść zadania.
Z każdego stanu da się dojść w czasie stałym do następnych. Trzeba tylko dokładnie rozpatrzeć przypadki (co mi się nie udało xD)


4 maja 2010, o 19:29
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 2 ] 


Kto przegląda forum

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


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