Rozwiązania zadań z finału


Poniżej zamieszczamy szkice rozwiązań zadań z eliminacji do zawodów. Zamieszczamy również same zadania oraz dane używane do sprawdzania zadań. Mamy nadzieję, że pomogą one się lepiej przygotować do kolejnej edycji zawodów.

Przy każdym zadaniu znajduje się jego typ, typy zadań są opisane w informacjach technicznych.

Pierwsza kategoria wiekowa (uczniowie szkół ponadgimnazjalnych)

B1: Bardzo Śmiały Złoczyńca

(zadanie deterministyczne)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Pobierz odpowiednio odległość jaką pokona złoczyńca , promień po którym będzie się poruszać , długość sznurka, do którego przywiązany jest Drybing , średnicę kołka  oraz punkty, w których może znajdować się dobytek Hamira.
  3. Oblicz ile obrotów wykona złoczyńca
  4. Oblicz nową długość na jaką może dostać się Drybing 
  5. Oblicz , gdzie to liczba wszystkich możliwych punktów ukrycia majątku Hamira.
  6. Wróć do kroku 1.

F1: Flota wojenna

(zadanie deterministyczne)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Zidentyfikuj nazwę strategii, odczytaj , oraz w przypadku formacji „Osa” .
  3. Oblicz odpowiednie prawdopodobieństwa
    ,
    ,

    .
  4. Wypisz wynik.
  5. Wróć do kroku 1.

G1: Gwiezdne wojny

(zadanie deterministyczne)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
    1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
    2. Zidentyfikuj nazwę strategii, odczytaj , oraz w przypadku formacji „Osa” .

    liczbę satelit , oraz punktów (współrzędnych ) z kolejnych linii.

  2. Zbuduj otoczkę wypukłą dla punktów.
  3. Wypisz wynik, jeśli otoczka wypukła składa się z punktów, odpowiedzią jest .
  4. Wróć do kroku 1.

Dowolna metoda budowania otoczki wypukłej działa, przykładowo:

  1. Budujemy początkowy ostrosłup wybierając cztery, niewspółpłaszczyznowe punkty, pozostałe punkty tworzą listę kandydatów.
  2. Jeśli lista kandydatów jest pusta, kończymy.
  3. Z listy kandydatów wybieramy punkt.
  4. Tworzymy listę ścian ostrosłupa widocznych z pobranego punktu i usuwamy je z ostrosłupa.
  5. Krawędzie ścian ostrosłupa, które stykały się z usuniętymi ścianami, łączymy z dodawanym punktem tak, aby tworzyły nowe ściany.
  6. Wracamy do kroku 1.

Dane o ostrosłupie możemy przechowywać przykładowo jako tablicę trójkątnych ścian (trzech liczb na ścianę) – ściana oznacza trójkąt powstały z połączenia punktów 1, 2 i 3.

K1: Kopalnia Nomadium

(zadanie deterministyczne)

W zadaniu należy wykonać kilka obliczeń zanim zabierzemy się do pisania programu. Załóżmy najpierw, że stoimy w pierwszej maszynie – wtedy z prawdopodobieństwem pozostaniemy przy tej samej maszynie, z prawdopodobieństwem przejdziemy do maszyny przebywając drogę , do maszyny przebywając drogę , itd aż do maszyny wykonując drogę . Nasza średnia przebytej drogi to . Jeśli natomiast zaczynamy od drugiej maszyny, możemy przejść do maszyny przebywając drogę , pozostać przy maszynie , przejść do maszyny wykonując drogę , itd aż do maszyny wykonując drogę . Ogólnie, jeśli zaczynamy od maszyny , średnia przebytej drogi to . Ponieważ nie wiadomo, od której maszyny zaczynamy, odpowiedzią jest (wykonanie ostatniego etapu obliczeń jest opcjonalne i jedynie przyśpieszy działanie programu)

.

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Odczytaj wartości oraz .
  3. Oblicz i wypisz na ekran wartość .
  4. Wróć do kroku 1.

T1: Tania Kolej Transsaturnowa

(zadanie deterministyczne)

W zadaniu należy wykonać kilka obliczeń zanim zabierzemy się do pisania programu.Zauważmy najpierw, że dla rozmieszczenia miast, trasy się nie przecinają. Oznaczmy . Wyobraźmy sobie teraz koło w którym rozmieszczone jest miast. Z miasta pociągnijmy trasę do miasta . Wtedy, pomiędzy miastem a wszystkimi miastami są trasy, które się przecinają z zaznaczoną trasą . Jeśli połączymy trasę , każde dwa punkty z łączą się z punktami . Podsumowując, połączeń wychodzących z miasta które się przecinają, jest . Ale to nie jest jeszcze cała wartość przecięć dla miast, ponieważ są trasy nie wychodzące z miasta . Zatem . Korzystając z założenia , mamy .

Łatwiejszą częścią zadania jest obliczenie wszystkich możliwych tras. Po pierwsze, istnieje możliwych połączeń, wystarczy spośród nich wybrać dwa dowolne: .

Odpowiedź to (wykonanie ostatniego etapu obliczeń jest opcjonalne i jedynie przyśpieszy działanie programu)

.

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Odczytaj wartości
  3. Oblicz i wypisz na ekran wartość .
  4. Wróć do kroku 1.

Druga kategoria wiekowa (studenci)

A2: Antractus nomadis

(zadanie deterministyczne)

Na wejściu programu mamy podany rozkład a priori dla nieznanego parametru oraz  realizację próby . Celem jest wskazanie, dla jakiego   prawdopodobieństwo  a posteriori jest największe. Postępujemy według następującego algorytmu:

  1. Wczytaj dane, o ile są dostępne na wejściu, bądź też zakończ działanie programu, jeśli nie ma więcej danych.
  2. Oblicz wielkości 
  3. Zwróć z punktu 2 dla którego wielkość przyjmuje największą wartość.
  4. Wróć do punktu 1. 

O2: Odyseja kosmiczna

(zadanie z testowania)

Z treści zadania wnioskujemy, ze na wejściu programu dostajemy sumy częściowe prób , , gdzie mają rozkłady dwupunktowe skupione w . Chcemy sprawdzić, czy i są niezależne. W tym korzystamy z testu Fishera, który jest testem dokładnym. Postępujemy według następujących kroków:

  1. Jeśli możesz, wczytaj dwie linia wejścia i przejdź do kroku nr 2. W przeciwnym wypadku zakończ działanie programu.
  2. Zróżnicuj dane z wejścia, aby dostać realizacje prób  .
  3. Wykonaj test niezależności Fishera. Jeśli na poziomie istotności 5% są podstawy, by hipotezę zerową odrzucić, wypisz 0, w przeciwnym wypadku zwróć 1.
  4. Przejdź do kroku 1.

P2: Poszukiwania Nomadium

(zadanie z estymacji)

Wnikliwa analiza treści zadania prowadzi do wniosku, że na wejściu dostajemy realizację próby losowej , gdzie mają rozkład będący mieszaniną dwóch rozkładów normalnych, tzn.  . Naszym celem jest znalezienie wielkości , co nie jest zadaniem łatwym, ponieważ parametry są nieznane. Można jednak rozwiązać ten problem maksymalizując funkcję wiarogodności dla próby , np. za pomocą znanego z literatury algorytmu EM. Rozwiązanie przedstawia się następująco:

  1. Jeśli dostępna jest linia wejścia, wczytaj ją i przejdź do punktu 2. W przeciwnym wypadku zakończ działanie programu.
  2. Za pomocą algorytmu EM znajdź – estymatory , .
  3. Na wyjściu programu zwróć  
  4. Przejdź do punktu 1.  

T2: Trzy, dwa, jeden, start!

(zadanie z estymacji)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Posortuj dane.
  3. Oblicz liczbę grup składających się z 50% obserwacji korzystając ze wzoru , gdzie stanowi długość pobranej próbki.
  4. Dla w zakresie od 1 do k policzyć odległość między elementami na pozycjach oraz .
  5. Zwróć najmniejszy otrzymany rozstęp.
  6. Wróć do kroku 1.

W2: Wielkie uszy królowej

(zadanie z testowania)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Odczytaj wektor wartości w postaci liczb, zamień na odpowiedni zapis binarny (zgodnie z treścią zadania) i zbuduj wektor zer i jedynek.
  3. Wykonaj test serii Walda-Wolfowitza (może być to również wersja asymptotyczna).
  4. Wypisz odpowiedź.
  5. Wróć do kroku 1.

Comments & Responses

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *