Rozwiązania zadań z eliminacji


Poniżej zamieszczamy szkice rozwiązań zadań z eliminacji do zawodów. Zamieszczamy również dane używane do sprawdzania zadań. Mamy nadzieję, że pomogą się lepiej przygotować do etapu finałowego. Przy każdym zadaniu znajduje się jego typ, typy zadań są opisane w informacjach technicznych.

Pierwsza kategoria wiekowa (uczniowie szkół ponadgimnazjalnych)

D1: Deszcze meteorytów

(zadanie deterministyczne)

Oznaczmy – Nadano (kropka, kropka, kropka), – Nadano (kreska, kreska, kreska), – Nadano (kreska, kropka, kreska), – Nadano (kropka, kreska, kropka), – Odebrano (kreska, kropka, kreska).

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Pobierz wiersz i zapisz je w postaci wektora oznaczającego
  3. Oblicz: , , , , , .
  4. Wypisz wynik .
  5. Wróć do kroku 1.

K1: Kosmologia

(zadanie deterministyczne)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Pobierz wiersz i przypisz wartość prawdopodobieństwa zmiennej .
  3. Oblicz .
  4. Wypisz wynik.
  5. Wróć do kroku 1.

S1: Skok nadprzestrzenny

(zadanie deterministyczne)

  1. Odczytaj i zapamiętaj całe wejście, jako oznaczamy największe z dostępnych wejść.
  2. Przygotuj listę możliwych skoków.
  3. Oblicz optymalne rozwiązania indukcyjnie, korzystając z założenia, że optymalnym rozwiązaniem skoku długości zero to zero skoków.
  4. Wypisz wszystkie rozwiązania dla odpowiadających im wejść.

Przykładowy algorytm przygotowania listy możliwych skoków:

  1. Stwórz tablicę zer .
  2. Dla każdego pod wartość podstaw , gdzie a jest takie, że i .
  3. Stwórz tablicę , gdzie oraz dla .
  4. Do listy możliwych skoków dodaj te długości , dla których .

Przykładowy algorytm optymalizujący:

  1. Stwórz tablicę rozwiązań . Niech .
  2. Dla każdego (w kolejności od najmniejszej do największej wartości) oblicz wartość na podstawie wartości – w tym celu, dla każdego możliwego skoku obliczonego wcześniej takiego, że , wybierz taki, który minimalizuje , czyli . Podstaw .

T1: Trójkąt Bermudzki

(zadanie deterministyczne)

Oznaczenia boków i trójkątów pochodzą od pierwszych liter nazw z zadania.

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. W trójkącie oblicz , gdzie to wysokość ściany bocznej (np. ) wychodząca z punktu , a to długość podstawy (np.: boku )
  3. Zauważ, że pole trójkąta jest równe polu trójkąta , z czego można policzyć wysokość ściany bocznej wychodzącą z punktu : , gdzie to długość boku .
  4. Stosując twierdzenie Pitagorasa oblicz , by ostatecznie ponownie stosując twierdzenie Pitagorasa obliczyć wysokość galaktyki: .
  5. Ponieważ „Trójkąt Bermudzki” i cała galaktyka mają tę samą podstawę, wysokość na jakiej znajduje się punkt jest proporcjonalna do wysokości całej galaktyki i wynosi , gdzie to prawdopodobieństwo wpadnięcia losowo wybranego punktu do Trójkąta Bermudzkiego.
  6. Wypisz wynik .
  7. Wróć do kroku 1.

W1: Wyłącznik gwiazd

(zadanie deterministyczne)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Można pokazać, że jedyne gwiazdy jakie będą świecić to te o numerach z nieparzystą liczbą dzielników. Takimi liczbami są tylko kwadraty liczb naturalnych, zatem należy zliczyć ile jest kwadratów liczb naturalnych do zadanej liczby. Rozwiązaniem tego zadania jest więc największa liczba naturalna mniejsza od pierwiastka z zadanej liczby. Oblicz .
  3. Wypisz wynik.
  4. Wróć do kroku 1.

Druga kategoria wiekowa (studenci)

A2: Atlas galaktyki

(zadanie z estymacji)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2.  Pobierz jeden wiersz i zapisz go w postaci wektora 
  3. Wyznacz niezbędną liczbę pomiarów dla próby na podstawie wzoru , gdzie jest kwantylem rozkładu normalnego.
  4. Wypisz wynik.
  5. Wróć do kroku 1.

C2: Czas dla bohatera

(zadanie z testowania)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Wczytaj dwie kolejne linie kodu jako dwa wektory. 
  3. Zamień logarytmując rozkład zmiennej odpowiadającej za odległość wystrzału na zmienną o rozkładzie normalnym.
  4. Przeprowadź test weryfikujący hipotezę o niezależności zmiennych losowych odpowiadających za kąt wystrzału i jego odległość.
  5. Wypisz wynik.
  6. Wróć do kroku 1.

D2: Droga mleczna

(zadanie z estymacji)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Wczytaj – liczbę z pierwszej linii oraz –  obserwacje zawarte w drugiej linii wejścia.
  3. Utwórz macierz , , , oraz wektor .
  4. Za pomocą metody najmniejszych kwadratów znajdujemy współczynniki odpowiedniego równania regresji przyjmując .
  5. Jako prognozę wartości zwracamy .
  6. Wypisz wynik .
  7. Wróć do kroku 1.

N2: Nomadium

(zadanie z estymacji)

  1. Sprawdź czy istnieją dane do pobrania. Jeśli tak to przejdź do kroku 2. Jeśli nie to koniec.
  2. Odczytaj linię ze znaków „-” i „+”. Zlicz odpowiednie znaki: oraz .
  3. Ponieważ liczba atomów jest z rozkładu Poissona, i , przy czym . Oblicz .
  4. Wypisz wynik .
  5. Wróć do kroku 1.

R2: Rozregulowany silnik

(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 liczbę linii testu
  3. Odczytaj linii wejścia do wektorów dla .
  4. Zadanie sprowadza się do wykonania testu omnibusowego w analizie wariancji. Ponieważ jest dużo obserwacji mocno odstających od średnich (ale prawidłowych, dane w plikach pochodzą jak można zauważyć z rozkładu log-Cauchy’ego), należy użyć procedury ANOVA Kruskall’a-Wallis’a.
  5. Wypisz wynik.
  6. 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 *