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 Oflimpiady 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.
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.
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?
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ć).