Olimpiada Informatyczna (XXII)

Data ostatniej modyfikacji:
2015-07-31
Autor: 
Paweł Świątkowski
student informatyki i filologii fińskiej UAM w Poznaniu
Organizator: 

Fundacja Rozwoju Informatyki
ul. Banacha 2, 02-097 Warszawa

http://www.oi.edu.pl

 

Terminy: 

06.10-03.11.2014 zawody I stopnia
10.02-12.02.2015 zawody II stopnia
15.04-18.04.2015 zawody III stopnia

28.04-03.05.2015 XXI Bałtycka Olimpiada Informatyczna, Warszawa
28.06-03.07.2015 XXII Olimpiada Informatyczna Europy Środkowej, Brno (Czechy)
26.07-02.08.2015 XXVII Międzynarodowa Olimpiada Informatyczna, Ałma-Ata (Kazachstan)

 

Uczestnicy Olimpiady Informatycznej muszą wykazać się wieloma umiejętnościami, gdyż rozwiązanie każdego zadania wymaga wyłuskania i wyspecyfikowania rzeczywistego problemu algorytmicznego ukrytego w treści, dyskusji możliwych rozwiązań (algorytmów) i wyborze najwłaściwszego, dobraniu odpowiednich struktur danych, zaprogramowaniu rozwiązania w wybranym języku programowania oraz dokładnym przetestowaniu stworzonego programu. Zatem etapy rozwiązywania takiego zadania są takie same jak w rozwiązywaniu rzeczywistych problemów, na jakie napotyka w swojej pracy zawodowy informatyk.

Nic dziwnego, że Olimpiada Informatyczna to jedne z najbardziej prestiżowych zawodów informatycznych w kraju. Zadania są trudne, wymagają dużej ilości czasu poświęconego na analizę, jednak satysfakcja z ich rozwiązania jest gwarantowana.

Laureaci biorą udział w Olimpiadzie Informatycznej Państw Europy Środkowej oraz w Międzynarodowej Olimpiadzie Informatycznej.

Od 2007 roku organizowana jest też Olimpiada Informatyczna Gimnazjalistów.

 

Historia: 

Zawody krajowe i środkowoeuropejskie odbywają się od 1994 roku, a międzynarodowe od 1989 roku (I edycja w Bułgarii).

Największe sukcesy Polaków na IOI:

  • Filip Wolski (III LO Gdynia) czterokrotnie zdobył złoty medal (2003, 2004, 2005, 2006).
  • Andrzej Gąsienica-Samek (XIV LO Warszawa) trzykrotnie zdobył złoty medal i raz srebrny (1996, 1997, 1998, 1999).
  • Marcin Andrychowicz (XIV LO Warszawa) trzykrotnie zdobył złoty medal (2006, 2007, 2008).
  • Piotr Zieliński (VIII LO Poznań) dwukrotnie zdobył złoty medal i raz srebrny (1995, 1996, 1997).
  • Tomasz Czajka (LO Stalowa Wola) dwukrotnie zdobył złoty medal i raz srebrny (1998, 1999, 2000).
  • Jarosław Błasiok (VIII LO Katowice) dwukrotnie zdobył złoty medal (2008, 2009).
  • Jarosław Kwiecień (XIV LO Wrocław) dwukrotnie zdobył złoty medal (2014, 2015).

http://en.wikipedia.org/wiki/International_Olympiad_in_Informatics#Multiple_IOI_winners

Sukcesy wrocławian:

  • Jarosław Kwiecień (GM 49, XIV LO) - brąz XX OI, złoto: XXI OI (I m), XXII OI (II m), złoto: IOI 2014, 2015
  • Agnieszka Dudek, Martyna Siejba, Mateusz Lewko (XIV LO) - brąz XXII OI
  • Jakub Zadrożny (III LO Wrocław) - wyróżnienie XXII OI
  • Jarosław Dzikowski, Adam Kuczaj, Maciej Kucharski, Martyna Siejba (XIV LO) - wyróżnienie XXI OI
  • Tomasz Syposz (XIV LO) - srebro XX OI (V m)
  • Daniel Danielski, Bartosz Kostka (XIV LO) - brąz XX OI
  • Kamil Niziński, Piotr Pietrzak (XIV LO) - wyróżnienie XX OI
  • Bartłomiej Dudek - (XIV LO) - braąz XVII OI, wyróżnienie XVIII OI, złoto XIX OI (3 m), srebro IOI 2012
  • Mateusz Gołębiewski (XIV LO) - srebro XVIII OI, złoto XIX OI (5 m)
  • Michał Łowicki (III LO) - brąz: XVII OI, XVIII OI, srebro XIX OI
  • Konrad Cichy (III LO), Michał Kownacki (XIV LO) - wyróżnienie XIX OI
  • Radosław Serafin (III LO) - brąz XVIII OI
  • Wojciech Kozaczewski (III LO) - wyróżnienie XVIII OI
  • Anna Piekarska (XIV LO) - brąz: XV OI, XVI OI, zloto XVII OI (4 m), srebro IOI 2010
  • Janusz Wróbel (XIV LO) - srebro XVII OI
  • Krzysztof Król (XIV LO) - wyróżnienie XVI OI, brąz XVII OI
  • Jan Marcinkowski (XIV LO) - brąz XVII OI
  • Dariusz Bukowski (XIV LO) - wyróżnienie XVII OI
  • Wiktor Janas (XIV LO) - srebro XVI OI
  • Adam Błaszkiewicz (XV LO) - wyróżnienie XVI OI
  • Jarosław Gomułka (XIV LO) - srebro XIV OI
  • Marcin Babij (IX LO) - brąz XIV OI
  • Mateusz Rukowicz (III LO) - srebro XIII OI
  • Krzysztof Templin (XIV LO) - wyróznienie XII OI
  • Michał Bartoszkiewicz (XIV LO) - brąz X OI
  • Tomasz Wawrzyniak (XIV LO) - brąz IX OI
  • Mateusz Kwaśnicki (III LO) - złoto VIII OI, srebro IOI 2001
  • Grzegorz Stelmaszek (XIV LO) - srebro VII OI, brąz VIII OI
  • Marcin Bieńkowski (XIV LO) - wyróżnienie IV OI
  • Marek Stocki (XIV LO) - złoto I OI (2 m), wyróżnienie II OI, brąz I0I 1994
  • Piotr Śniady (XIV LO) - brąz I OI.

 http://stats.ioinformatics.org/halloffame/POL

 

Skrót regulaminu: 
  • Olimpiada składa się z 3 etapów.
  • Pierwszy polega na samodzielnym rozwiązaniu zadań i przesłaniu ich do organizatora za pomocą internetu.
  • Etap II - regionalny i III - finał ogólnopolski odbywają się w ustalonych miejscach w warunkach kontrolowanej samodzielności.
  • Tytuł finalisty lub laureata zwalnia z matury z informatyki oraz daje wolny wstęp na większości polskich uczelni na kierunki związanie z matematyką i informatyką.

 

Przykładowe zadania: 

Liczby antypierwsze. Dodatnią liczbę całkowitą nazywamy antypierwszą, gdy ma ona więcej dzielników niż każda dodatnia liczba całkowita mniejsza od niej. Przykładowymi liczbami antypierwszymi są: 1, 2, 4, 6, 12 i 24.

Napisz program, który:

  • wczyta z pliku tekstowego ANT.IN dodatnią liczbę całkowitą n,
  • wyznaczy największą liczbę antypierwszą nie przekraczającą n,
  • zapisze wyznaczoną liczbę w pliku tekstowym ANT.OUT.

Wejście. W jedynym wierszu pliku tekstowego ANT.IN znajduje się jedna liczba całkowita n,
1 <= n <= 2 000 000 000.

Wyjście. W jedynym wierszu pliku ANT.OUT program powinien zapisać dokładnie jedną liczbę całkowitą - największą liczbę antypierwszą nie przekraczającą n.

Przykład. Dla pliku wejściowego ANT.IN: 1000
poprawną odpowiedzią jest plik wyjściowy ANT.OUT: 840

 

Połączenia. Ministerstwo Infrastruktury Bajtocji postanowiło stworzyć program pozwalający szybko obliczać długości tras między dowolnymi miastami. Nie byłoby w tym nic dziwnego, gdyby nie fakt, iż mieszkańcy Bajtocji nie zawsze szukają najkrótszej trasy. Zdarza się, że pragną dowiedzieć się o k-tą co do długości najkrótszą trasę. Dopuszczamy zapętlenia tras, tzn. takie trasy, na których miasta powtarzają się.

Przykład. Jeśli między dwoma miastami istnieją 4 trasy o długościach: 2, 4, 4 i 5, to najkrótsze połączenie ma długość 2, drugie co do długości 4, trzecie 4, a czwarte 5.

Napisz program, który:

  • wczyta ze standardowego wejścia opis sieci dróg Bajtocji oraz zapytania dotyczące długości tras przejazdu,
  • obliczy i wypisze na standardowe wyjście odpowiedzi do wczytanych zapytań.

Wejście. W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite n i m oddzielone pojedynczym odstępem, 1 <= n <= 100, 0 <= m <= n2-n. Są to odpowiednio liczba miast w Bajtocji oraz liczba dróg łączących miasta. Miasta są ponumerowane od 1 do n. W każdym z kolejnych m wierszy znajdują się po trzy liczby całkowite oddzielone pojedynczymi odstępami: a, b i d, a <> b, 1 <= d <= 500. Każda taka trójka opisuje jedną, jednokierunkową drogę długości d umożliwiającą przejechanie z miasta a do b. Dla każdych dwóch miast istnieje co najwyżej jedna droga umożliwiająca przejazd w danym kierunku. W kolejnym wierszu znajduje się jedna liczba całkowita q, 1 <= q <= 10000, oznaczająca ilość zapytań. W kolejnych q wierszach są zapisane zapytania, po jednym w wierszu. Każde zapytanie to trzy liczby całkowite oddzielone pojedynczymi odstępami: c, d i k, 1 <= k <= 100. Zapytanie takie dotyczy długości k-tej najkrótszej trasy z miasta c do miasta d.

Wyjście. Program powinien wypisywać odpowiedzi na wczytane zapytania na standardowe wyjście, po jednej odpowiedzi w wierszu. W i-tym wierszu powinna zostać wypisana odpowiedź na i-te zapytanie - jedna liczba całkowita równa szukanej długości trasy lub -1, gdy taka trasa nie istnieje.

Przykład. Dla danych wejściowych:
5 5
1 2 3
2 3 2
3 2 1
1 3 10
1 4 1
8
1 3 1
1 3 2
1 3 3
1 4 2
2 5 1
2 2 1
2 2 2
1 1 2
poprawnym wynikiem jest:
5
8
10
-1
-1
3
6
-1
 

Powrót na górę strony