Jak Bajtek machiny skomplikowane konstruował

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Jak Bajtek machiny skomplikowane konstruował

Postautor: witman » 21 paź 2013, 22:10

Potrzebna wiedza: Przeszukiwanie grafu w głąb lub wszerz, konwersja z systemu dwójkowego na ósemkowy.

Budujemy graf, w którym koła zębate są wierzchołkami, a przekładnie krawędziami.
Na temat każdego wierzchołka musimy mieć możliwość przechowywania informacji o kierunku obrotów i ilorazu szybkości w stosunku do koła nr 1. Ponieważ ten iloraz szybkości jest zawsze potęgą dwójki, to wystarczy przechowywać tylko wykładnik tej potęgi (nazwijmy go W).
Zaczynając od koła nr 1 (który ma kierunek zgodny i prędkość jednostkową, czyli W=0) uruchamiamy BFS lub DFS. Dochodząc do jakiegoś wierzchołka (koła), na podstawie parametrów wierzchołka-poprzednika i rodzaju przekładni możemy wyznaczyć kierunek obrotów tego koła (taki sam lub przeciwny) oraz wykładnik W (większy lub mniejszy o 1 od wartości W wierzchołka poprzednika). Jeśli ten wierzchołek jest odwiedzany po raz pierwszy to zapisujemy "w nim" wyznaczone wartości. Jeśli ten wierzchołek był już odwiedzony wcześniej, to porównujemy zapisane w nim parametry z tymi dopiero co obliczonymi. Jeśli nie ma zgodności, to przeszukiwanie można przerwać, ponieważ "TA MASZYNA DO RUCHU NIE JEST ZDOLNA!". Jeśli przeszukamy cały graf i nie będzie niezgodności to "TEN PROJEKT JEST DOBRY!".
Przy wypisywaniu (dla działającej maszyny) informacji o potrzebnych zębatkach, zachodzi konieczność podania szybkości w systemie ósemkowym. Jednak mając dla koła wyliczony wykładnik W, podanie liczby 2^W w systemie ósemkowym jest trywialne: wynik to cyfra od 1, 2 lub 4, po której następuje odpowiednia liczba cyfr "0".

Z uwagi na ograniczony do 8MiB rozmiar stosu, nie moża zastosować DFS'a opartego na funkcji rekurencyjnej.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 1 gość

cron