Zadania Olimpiady Informatycznej

Zadania na Olimpiadzie Informatycznej są typu algorytmiczno-programistycznego. Rozwiązując zadanie, musimy wyłuskać właściwy problem algorytmiczny z historii opisanej w treści zadania, wymyślić rozwiązanie do tego problemu, a następnie to rozwiązanie zapisać w postaci programu w jednym z wskazanych języków programowania. Rozwiązanie jest sprawdzane automatycznie za pomocą testów poprawnościowych oraz wydajnościowych i oceniane według punktacji opisanej w treści zadania. Serwis sprawdzający rozwiązania z archiwum Olimpiady Informatycznej znajduje się pod adresem https://szkopul.edu.pl/.

Do każdego zadania może istnieć wiele rozwiązań, w tym też takie, których wykonanie trwa kilka dni lub nawet wiele lat - takie rozwiązania są za wolne. Główną trudnością jest wymyślenie i zapisanie poprawnego rozwiązania, które wykonuje się w kilka sekund. Wymaga to umiejętności korzystania ze znanych "cegiełek algorytmicznych" oraz dostrzegania unikalnych własności zadania, które przydają się do szybkiego rozwiązania zadania.

Dlaczego na Olimpiadzie Informatycznej nie ma zadań z baz danych, projektów programistycznych albo stron internetowych? Takie zadania wymagają znajomości większej ilości narzędzi oraz wymagają odpowiedniej wiedzy technicznej, która co roku się zmienia. Niekoniecznie da się rozwiązania takich zadań ocenić obiektywnie - mógłby się liczyć styl kodu, zwięzłość rozwiązania, aspekt artystyczny lub wykorzystana technologia. Zadania algorytmiczne są oceniane tylko na podstawie tego, na ile efektywne rozwiązanie wymyślił uczestnik oraz czy je poprawnie zaimplementował. Przy tym styl kodu źródłowego nie jest oceniany - przydaje się przede wszystkim do sprawniejszego znajdywania błędów w kodzie i szybszego pisania rozwiązań.

Taki sam typ zadań jest używany na międzynarodowych zawodach, takich jak Międzynarodowa Olimpiada Informatyczna (IOI) albo Środkowoeuropejska Olimpiada Informatyczna (CEOI).

Żeby rozwiązywać zadania na Olimpiadzie Informatycznej, trzeba wykazać się umiejętnością myślenia oraz programowania. Z tego względu prostsze warianty takich zadań są używane przez firmy (takie jak Google, Amazon, Apple, Meta, Microsoft) na rozmowach rekrutacyjnych na stanowisko programisty - nauczenie się rozwiązywania takich zadań może pomóc w zdobyciu dobrej pracy!

Znajomość algorytmów oraz struktur danych przekłada się na możliwość tworzenia skomplikowanych systemów współbieżnych, protokołów sieciowych, jak i do rozwiązywania problemów medycznych. Wielu byłych uczestników Olimpiady Informatycznej osiąga ponadprzeciętne wyniki na studiach licencjackich, magisterskich, jak i w późniejszej karierze zawodowej i naukowej. Wreszcie najważniejsze pytanie otwarte w informatyce teoretycznej jest z natury algorytmiczne - nazywa się "P versus NP" i jest problemem milenijnym, za którego ogłoszono milion dolarów nagrody.

Poniżej znajdują się przykładowe zadania z wcześniejszych edycji Olimpiad Informatycznych. Lista wszystkich zadań z Olimpiady Informatycznej znajduje się tutaj.

Sprawdź się!

Trudność     
Zadanie Farma z I etapu XVI Olimpiady Informatycznej Juniorów.
Sprawdź pełną treść i przetestuj rozwiązanie.
Szczegółowy opis rozwiązania znajduje się na stronie OIJ

Na farmie Bajtka jest pewna liczba kur i krów. Razem wszystkie te zwierzęta mają dokładnie \(X\) głów oraz \(Y\) nóg.

  • Ile kur oraz ile krów ma Bajtek, jeśli \(X = 4,\; Y = 12\)?
  • Co jeśli \(X,\;Y\) to dowolne liczby spełniające \(1 \le X, Y \le 1\,000\,000\,000\)?
  • Trudność     
    Zadanie Litery z I etapu XIX Olimpiady Informatycznej.
    Sprawdź pełną treść i przetestuj rozwiązanie.
    Szczegółowy opis rozwiązania znajduje się w niebieskiej książeczce XIX OI

    Dane są dwa napisy, w których każda litera występuje po tyle samo razy. W jednej operacji można zamienić dwie sąsiednie litery pierwszego napisu. Na przykład, można zamienić napis ABCA na BCAA w dwóch ruchach.

  • W ilu minimalnie ruchach można zamienić nazwisko OWCZARSKI na nazwisko SARKOWICZ? Albo OLKIEWICZ i WIELICZKO?
  • Co jeśli oba napisy składają się z \(1\,000\,000\) liter?
  • Trudność     
    Zadanie Most z II etapu XI Olimpiady Informatycznej.
    Sprawdź pełną treść i przetestuj rozwiązanie.
    Szczegółowy opis rozwiązania znajduje się w niebieskiej książeczce XI OI

    Turyści mają jedną latarkę i chcą przejść przez stary most. Światło latarki umożliwia przejście przez most maksymalnie dwóm turystom na raz. Turyści nie mogą przechodzić przez most bez latarki, ani w większych niż dwuosobowych grupach. Każdemu turyście przejście przez most zajmuje określony czas. Dwóch turystów idących razem potrzebuje na przejście przez most tyle czasu, co wolniejszy z nich. Jaki jest najkrótszy czas, w którym wszyscy turyści mogą przejść przez most?

  • Przypuśćmy, że grupa liczy czterech turystów, którzy potrzebują na przejście kolejno 6, 7, 10 oraz 15 minut. Turyści mogą przejść przez most w 44 minuty: najpierw przechodzą osoby potrzebujące 6 i 7 minut, co zajmuje im 7 minut, wraca osoba 6, przechodzą osoby 6 i 10, wraca osoba 6, przechodzą osoby 6 i 15. Mogą to jednak zrobić jeszcze szybciej, łącznie w 42 minuty. Jak?
  • Co jeśli jest \(100\,000\) turystów, każdy z czasem przejścia z zakresu \(\{1,2,\dots,1\,000\,000\,000\}\)?
  • Trudność     
    Zadanie Sumy z III etapu X Olimpiady Informatycznej.
    Sprawdź pełną treść i przetestuj rozwiązanie.
    Szczegółowy opis rozwiązania znajduje się w niebieskiej książeczce X OI

    Mamy dany zbiór dodatnich liczb całkowitych \(A = \{a_1, a_2, \ldots, a_n\}\). Zbiór \(B\) nazywamy zbiorem sum zbioru \(A\), jeśli liczba \(x\) należy do \(B\) wtedy i tylko wtedy, gdy \(x\) jest sumą pewnych elementów z \(A\) (elementy mogą się powtarzać).

  • Dla \(A = \{2, 5, 7\}\) liczby \(4\) oraz \(9\) należą do \(B\), ale liczba \(1\) już nie. Czy liczba \(11\) należy do \(B\)? Jaka jest największa liczba nienależąca do \(B\)?
  • Co jeśli \(n \le 5\,000,\; a_i \le 50\,000\) oraz należy stwierdzić, czy podane \(5\,000\) liczb z zakresu \(1,2,\dots,1\,000\,000\,000\) należy do \(B\)?