NOMAD (IX)

ELIMINACJE

szkoły ponadgimnazjalne

Deszcz meteorytów. Podczas podróży kosmicznej jeden z nomadów podróżujący statkiem Dromader 13 wpadł w deszcz meteorytów. Aby zwiększyć swoje szanse przeżycia, musi poinformować pozostałych o swoim problemie — być może będą potrafili mu pomóc. Może to zrobić, przesyłając wiadomość za pomocą alfabetu Morse’a. Wiadomość taka składa się z 3 sygnałów. Nomad może nadać 4 rodzaje informacji:
kropka-kropka-kropka — koniec paliwa,
kreska-kreska-kreska — atak obcych,
kreska-kropka-kreska — deszcz meteorytów,
kropka-kreska-kropka —czarna dziura.
Wiadomości te wysyła się odpowiednio za pomocą przycisków I, II, III lub IV. Z powodu turbulencji nomad naciśnie guzik I z prawdopodobieństwem p₁, II z p_2, III z p₃ lub IV z p₄. Sygnały podlegają jednak losowym zakłóceniom przez pył kosmiczny. W rezultacie sygnał 'kropka' może być odebrany jako 'kreska' z prawdopodobieństwem k, zaś sygnał 'kreska' może być odebrany jako 'kropka' z prawdopodobieństwem l. Nomadowie zbadali, że sygnały 'kropka' i 'kreska' są poddawane zniekształceniom niezależnie. W nomadzkiej bazie odebrano sygnał kreska-kropka-kreska. Jakie jest prawdopodobieństwo, że została nadana informacja o rzeczywistych kłopotach nomada? Wejście składa się z jednej linii, w której podane są prawdopodobieństwa p₁, p_2, p_3, p₄, k, l.

Przykładowe wejścia:
0.2370 0.1880 0.3280 0.2470 0.1100 0.0709
0.2750 0.0790 0.3420 0.3040 0.1920 0.3260
Przykładowe wyjścia:
0.9460071
0.8496416

szkoły wyższe

Droga mleczna. Gospodarka kosmicznych nomadów, podobnie jak ich ziemskich braci, opiera się głównie na hodowli wielbłądów. Międzygalaktyczni koczownicy traktują te zwierzęta jak członków rodziny, czemu trudno się dziwić — z mleka kosmicznych wielbłądów można wyprodukować nomadinę — wysokoenergetyczne paliwo dla statków, które postacią przypomina najzwyklejszą we wszechświecie bryndzę. Niestety, kosmiczne wielbłądzice nie należą do najbardziej ugodowych, więc bardzo trudno jest o to, by dostawy ich mleka zawsze osiągały oczekiwany poziom. Okazuje się, że skłonność wielbłądzic do współpracy można w pewnym stopniu przewidzieć. Raszyd Selim Al-Malouf, nomadzki businessman, który zbił majątek na handlu wielbłądzim mlekiem, twierdzi, że ilość mleka wyprodukowanego danego dnia zależy w sposób liniowy od kilku ostatnich wartości tego wskaźnika, a zależność ta jest niezmienna w czasie. Jakby tego było mało, Raszydowi wystarcza tylko chwila przypatrywania się danym dotyczącym produkcji, aby stwierdzić, jaki jest jej rząd wspomnianej zależności. Wiedzę tę można wykorzystać, by na podstawie zaobserwowanych danych przewidzieć, ile mleka można będzie wyprodukować w przyszłości. Pojedyncze wejście programu składa się z dwóch linii. Pierwsza informacja to wskazówka Raszyda — liczba ostatnich obserwacji mających wpływ na wskaźnik produkcji mleka. Druga linia to dane dotyczące produkcji z k kolejnych dni. Zadaniem jest zaprognozowanie ilości wyprodukowanego mleka w dniu k + 1.

Przykładowe wejścia:
2
67.830 67.699 65.745 67.544 63.300 63.287 63.227 67.012 69.281 71.892 70.993 71.086 70.557
3
130.9174 120.2749 126.2859 123.4186 124.3474 123.8648 123.2041 123.7942 124.9461
Przykładowe wyjścia:
70.895
124.181

FINAŁ

szkoły ponadgimnazjalne

Flota wojenna. NASA (Nomad Aeronautics and Space Administration) na zlecenie dowódcy Damona przygotowuje flotę wojenną na wypadek ataku ze strony obcych cywilizacji. NASA rozważa rozmieszczenie k uzbrojonych statków kosmicznych w n oddziałach. Jednostki wysyłane będą do walki oddział po oddziale, możliwe jest również wzięcie wroga na przeczekanie, co aby nie komplikować instrukcji dla pilotów, NASA również nazywa zero-osobowym oddziałem. W zależności od rodzaju uzbrojenia statków obecny plan przewiduje, że możliwa jest jedna z trzech następujących strategii:
1. Dell Nomadell to strategia, w której statki różnią się między sobą pod względem uzbrojenia. Przesunięcie jednostki między oddziałami daje zatem nową formację. Liczba statków w jednym oddziale jest dowolna.
2. Osa Nomadosa to strategia, w której statki mają identyczne uzbrojenie. Zamiana dwóch jednostek miejscami nie zmienia formacji.
3. Dino Nomadino to strategia, w której statki nie różnią się miedzy sobą, a w każdym oddziale może znaleźć się co najwyżej jeden statek.
NASA zastanawia się, czy rozsądne jest, aby piloci sami wybierali sobie formację w jakiej lecą. Wiadomo, że wielu z nich to indywidualiści i możliwe jest, że będą tworzyć oddziały jednoosobowe, czyli będą tak zwanymi wolnymi strzelcami. O ile wolni strzelcy są potrzebni w każdej formacji, ważne są też większe, współpracujące ze sobą oddziały. Najbardziej niekorzystne rozstawienie statków to tak zwany Rząd Straceńców czyli formacja, w której wszystkie jednostki pełnią rolę wolnych strzelców i znajdują się jeden po drugim na początku formacji. Oczywiście, Damon tego nie chce, zatem zlecił Ci obliczenie prawdopodobieństwa, że gdy pilotom pozostawić wolny wybór, ustawią się w Rząd Straceńców.
Ponieważ od dawna nie dostałeś podwyżki, chcesz wykonać nieco dodatkowej pracy, by mieć jakieś podstawy do negocjacji nowej stawki. NASA nagradza aktywnych! Zauważyłeś, że w przypadku formacji Osa Nomadosa korzystne jest pojawienie się tak zwanej tarczy, czyli pewnej liczby jednostek lecących w ostatnim oddziale. Zatem do każdej analizy strategii Osa Nomadosa, postanowiłeś dodatkowo obliczać, jakie jest prawdopodobieństwo, że w ostatnim oddziale znajdzie się dokładnie m statków, nie biorąc pod uwagę, jak rozmieszczą się pozostałe jednostki. Wejście składa się z wielu przypadków, po jednym w linii. W każdej linii podana jest odpowiednio: liczba oddziałów, liczba statków i skrócona do pierwszego członu nazwa strategii. W przypadku wybrania strategii Osa Nomadosa podana jest dodatkowo liczba m statków w tarczy.

Przykładowe wejścia:
3 2 Dell
5 4 Osa 3
Przykładowe wyjścia:
0.222222222222
0.0142857142857 0.0571428571429

szkoły wyższe
Odyseja kosmiczna. Pilot statku kosmicznego to zawód cieszący się ogromnym poważaniem w społeczności nomadów, trudno się więc dziwić, że tak wielu młodych śmiałków pragnie zostać adeptami sztuki pilotażu. Niestety, nie każdy posiada zdolności do wykonywania tego zawodu, a co gorsza, ostatnimi czasy nie wszystkie niedorajdy udaje się wykluczyć podczas wyboru kandydatów na pilotów. Nomadzcy naukowcy postanowili znaleźć sposób, by skuteczność selekcji zdecydowanie poprawić. Naukowcy zaprojektowali więc wirtualną Nomadię. W tym nierzeczywistym świecie można poruszać się tylko po dwuwymiarowej kracie całkowitej, która w każdym punkcie wygląda tak samo. Kandydat na starcie w punkcie (0, 0) dowiaduje się, w którym kierunku powinien podążać. Następnie w chwilach i = 1, ... , n porusza się o jeden na wschód bądź zachód (Xi) oraz o jeden na północ bądź południe (Yi). Już po kilku krokach można wywnioskować, czy testowany nadaje się na pilota — jeśli badany jest zdolny zostać asem międzygalaktycznych przestworzy, to ciągle pamięta o celu podróży, dlatego jego wertykalne i horyzontalne decyzje są zależne.
Każde dwie linie wejścia programu to kolejno x-owe i y-owe współrzędne położenia danego kandydata w wirtualnej Nomadii. Na wyjściu zwróć 1, jeśli decyzje kandydata były zależne. W przeciwnym wypadku zwróć 0.

Przykładowe wejścia:
1 0 1 0 1 0 1 2 1 2 1 2 3 4 3 2 1 0
-1 -2 -3 -4 -3 -4 -3 -2 -3 -4 -5 -6 -5 -6 -5 -4 -3 -2
-1 0 -1 0 1 2 3 2 1 2 3 2 3 4 5 4
1 2 3 4 3 2 3 4 5 4 3 4 5 4 3 4

Przykładowe wyjścia:
0
1