Komitet Główny Uczelnianej Partii Inteligencji Pracującej zlecił badania nad treningiem polepszajacym kodycję fizycną pracowników uczleni wyższych. Na teren treningów, którym każdy pracownik dydaktyczno-naukowy winien od przyszłego tygodnia poświecać się przynajmniej raz dziennie, wybrano Park Jordana. W związku z tym, że ilość pracowników uczleni jest bardzo duża, konieczne jest zaprogramowanie treningu, tak aby tłok na alejkach parkowych był jak najmniejszy, ale jednocześnie, aby trening był optymalny. Każdy Inteligent otrzyma na starcie najnowsze wydanie książki „W prowadzenie do Algorytmów” Cormena i z tą ksiażką (oczywiscie czytając ją podczas biegu, aby nie marnowac cennego czasu) będzie musiał biegać alejkami tak, aby pokonać jak najdłuższy dystans, ale jednocześnie nie przechodzić dwa razy tą samą ścieżka, co utrudniałoby trening innym i zwiekszało ruch na niektóych wąskich alejakch. Napisz program, który rozwiąże ten problem. Dobrze by było żeby trasa treningu przecinała się w minimalnie niewielu punktach, żeby roztargnieni naukowcy nie wpadali na siebie…

Uwaga - Do wyznaczenia odległości w parku można użyć na przykład http://www.openrouteservice.org/, iść na rower i zmierzyć odległości licznikiem rowerowym, ewentualnie wybrać się na rolki/spacer/jogging z dziewczyną/chłopakiem/psem lub w skrajnym przypadku - samemu- i z użyciem GPS-a zmierzyć odpowiednie odległości.

Popularną stała się ostatnio gra telewizyjna w której gracz dostaje kilka-kilkanaście liter, porozrzucanych w losowej kolejności i musi ułożyć z nich wyraz. Napisz program, który umożliwi Partii Inteligencji Pracującej wygrywanie teleturnieju. Program powinien na podstawie podanego zbioru liter wyświetlić wszystkie wyrazy jakie można z niego ułożyć w czasie O(n).

Do rozwiązania w postaci programu komputerowego załącz analizę złożoności.

Nasz Towarzysz Bustin Jieber planuje trasę koncertowa. Maksymalnie jednego dnia może zagrać 4 koncerty, ale po każdym koncercie musi wrócić do hotelu żeby zadenuncjować fanów którzy nie dość ekspresyjnie wyrażali swoją radość podczas gdy śpiewał o sukcesach Partii Inteligencji Pracującej. Oczywiście aby zminimalizować koszty przejazdu konieczne jest zaplanowanie każdej trasy w następujący sposób:

1. dla otrzymanej mapy reprezentującej połączenia pomiędzy miastami wyznaczyć takie zbiory miast między którymi komunikacja będzie optymalna 9będzie można dostać się do każdego z nich i jednocześnie wrócić zawsze do hotelu (także umieszczonym w którymś z miast).
2. wewnątrz zbiorów określić trasę i miast w których Jieber będzie stacjonował w hotelu
3. w obrębie zbiorów miast wyznaczyć trasę pomiędzy nimi tak, aby była optymalna.