Zad2 - Szukanie Kontenerów w Porcie

Objęłaś(objąłeś) stanowisko kierownicze w pewnym porcie. Zostałaś wybrana(y) ze względu na umiejętności algorytmiczne, którymi miałaś(eś) okazję wykazać się w poprzednich przedsięwzięciach optymalizując czas pracy, wydajność pracowników, obniżając koszty, ogólnie optymalizując działanie całości organizacji jako złożonych systemów.

Kolejnym zadaniem jest Port dla statków handlowych.

Dziś kolej na uporanie się z problemem "Pana szukającego kontenera". Jako, iż pracownicy są kluczowym elementem każdej organizacji, ułatwiając im pracę, zmniejszamy zmęczenie, stres a zarazem podnosimy efektywność i motywację do pracy.

Jako, iż z problemem "Pana szukającego kontenera" w waszym porcie Panowie od załadunku spotykają się codziennie, tak więc jest bardzo dobrym do optymalizacji. (Problem "Pana" szukającego kontenera spotyka czasami również Panie pracujące w porcie, jednak został tak nazwany, gdyż zwykle spotyka Panów pracujących przy załadunku, podczas gdy Panie pracują zwykle w innych działach).

Problem "Pana szukającego kontenera" został zdefiniowany w dokumencie o tej samej nazwie i uchwalony przez zarząd Portu już rok temu.

Problem dotyczy każdego pracownika, który chce znaleźć kontener w porcie.

Port rozciąga się wzdłuż brzegu, kontenery są ustawione w jednej linii wzdłuż wybrzeża. Kontenery są bardzo duże. Sprawdzenie czy dany kontener to ten, wymaga czasu potrzebnego na przeczytanie oznaczeń na kontenerze. Przejście od jednego do kolejnego zajmuje czas (kontenery są naprawdę duże). Tak samo z daleka możemy tylko odczytać oznaczenia do kilku kontenerów dalej, jeżeli są za daleko trzeba podejść co też zajmuje czas . Zanim odnajdziemy odpowiedni kontener, często musimy sprawdzić co najmniej kilka, a każde sprawdzenie wymaga czasu.

Czas spędzony na znalezienie kontenera, jest więc spędzony na sumie czasu na chodzenie pomiędzy kontenerami, sprawdzanie kontenerów. Ponieważ widać do kilku kontenerów w dal, podchodzimy na tyle blisko by móc go dojrzeć.

Zarząd wiedząc, jak złożoną czynnością jest szukanie kontenera zarządził by kody identyfikacyjne kontenerów były ułożone rosnąco (od lewego do prawego kontenera stojąc tyłem do morza, przodem do kontenerów). Zawsze kiedy ten porządek zostanie zaburzony na skutek odstawiania, dostawiania kontenerów, są numerowane od nowa.

Ty, widząc iż, sprawdzanie wszystkich po kolei owocuje zbytnią stratą czasu, natomiast poszukiwanie binarne powoduje zbytnie straty czasu na chodzenie, zaproponowałaś(eś) specjalną proceduję. (Dlaczego natomiast szukając sekwencyjnie w średnim wypadku mniej się nachodzimy, a poszukując binarnie mniej wykonamy porównań, dobrze wiesz z wykładu o Algorytmach i Strukturach Danych na PJWSTK ;) - przecież z tego powodu Cię wybrano na to stanowisko! Zadanie optymalizacji całego Portu! Ale skupmy się z powrotem na obecnym problemie… ).

Procedura jest następująca. Pan szukający kontenera, zaczyna poszukiwania od lewego (niech kontenery będą numerowane od 0). Idzie sprawdzić k-ty kontener. Jeżeli to nie ten to idzie sprawdzić kolejny o k dalej (2*k) i powtarza czynność (sprawdzając 3*k, 4*k…) aż trafi na pierwszy który znajduje się "za" poszukiwanym kontenerem. Niech to będzie kontener l*k. Od tego momentu przechodzi w tryb poszukiwań binarnych pomiędzy (l-1)*k, a l*k-tym kontenerem. Pamiętajmy, że aby sprawdzić dany kontener idziemy tylko jak się znajduje poza zasięgiem wzroku i podchodzimy na tyle blisko by móc go dostrzec(a nie pod sam sprawdzany kontener).

Problem jest taki, iż pracownicy nie potrafią wyznaczyć optymalnego k, a jest ono różne w zależności od odległości z jakiej są w stanie dostrzec kontener.

Wdróż swoje nowe procedury oraz uniknij frustracji przy ich wprowadzaniu dostarczając pracownikom rozwiązania, które poda im jakie k jest dla nich najlepsze !

W pierwszej linii mamy liczbę pracowników n oraz ilość kontenerów w porcie m.

W kolejnych n liniach mamy dla każdego pracownika:

n*m³ =< 10’000’000

0 =< o =< m

0 =< p,r =< 1000

(Wszystkie liczby są całkowite)

Pracownik zaczyna stojąc przy pierwszym z lewej kontenerze.

Pracownik szuka kontenera po kodzie, a kontenery są ustawione od lewej, kodami rosnąco.

Pracownik stojąc przy i-tym kontenerze widzi kontenery o numerach i - o…i + o (włącznie).

Pracownik jeżeli chce sprawdzić j ty kontener, zaczyna się poruszać tylko jeżeli jest on poza jego polem widzenia. Jeżeli, tak jest, to idzie, tylko tyle, ile musi by zobaczyć kontener (czyli odpowiednio do j - o lub j + o).

Pracownik zgodnie z procedurą sprawdza najpierw co k-ty kontener, zaczynając od 1 * k…. jeżeli po sprawedzeniu j-tego kontenera , chce iść do j + k tego i okazuje się że j + k >= m , to zmierza sprawdzić m - 1 szy (ostatni z prawej).

Kiedy pracownik odkryje, sprawdzając co k-ty kontener, że przekroczył poszukiwany, to przechodzi w tryb poszukiwania binarnego. Tutaj są dwa przypadki:

Te dwa przypadki mają na celu zagwarantowanie byśmy w drugiej fazie sprawdzali tylko jeszcze nie rozpatrywane kontenery.

Pracownik zmieniając pozycję o jeden kontener (np. z i do i + 1) zużywa p czasu. Czyli idąc od kontenera i do kontenera j zużywa | j - i | * p czasu.

Pracownik sprawdzając kontener (jego kod) zużywa r czasu.

Dla każdego pracownika (dla każdej trójki { o, p, r } ), trzeba dobrać takie k by pracownik miał jak najniższy oczekiwany (średni) czas odszukania kontenera. W przypadku, jeżeli dla kilku różnych k osiąga najniższą wartość oczekiwaną, należy wybrać spośród nich największe k.

Wyjście ma n linii.

W i-tej linii podajemy k dobrane dla i-tego pracownika.

(Czyli jest to n liczb, każda w oddzielnej linii.) (Liczby są całkowite.)

Pamięciowe: W tym zadaniu wystarczy malutko pamięci, dlatego limit będzie nieduży… z założenia nie powinniście potrzebować więcej, jak zablokować tablicę (ew. kilka) o wielkości m elementów. (Można i bez tego się obyć, ale nie zabraniam zablokować tablicy (ew kilku).)

Te co ostatnio.

Pamiętajcie testując przed wysłaniem rozwiązanie na ideone.com, aby zaznaczać opcję "private", co uchroni wasze rozwiązanie przed kradzieżą.

Czytasz pewnie wiele stron www, czy treści zadań takie jak To. Może być Tobie wygodniej czytać z inną czcionką, bądź układzie kolorystycznym. Kolor, krój czcionki, interlinia, szerokość kolumny tekstu mają szczególne znaczenie przy różnych dysfunkcjach, ale nie tylko ! Takie zmiany mogą zmniejszyć napięcie w gałce ocznej podczas długiej pracy z monitorem, wpłynąć na zdrowie oka, samopoczucie.

Jeżeli takie optymalizacje mogą pomóc Tobie w czytaniu, zachęcam do spróbowania bookmarkletów (można zrobić nowy guzik w przeglądarce na zasadzie linka) moje ulubione:

(Ja np. preferuję schemat białe na czarnym oraz wąską kolumnę).