Olimpiada Informatyczna krok po kroku – Tutorial – Przygotuj się sam!

Chcesz wystartować w Olimpiadzie Informatycznej Szkół Średnich (OI) lub w Olimpiadzie Informatycznej Juniorów Szkół Podstawowych (OIJ)?

ZAPRASZAM do wspólnej przygody!

Zaczynamy od zera!
Nic nie umiesz? Nawet programować?
Nie wiesz jak zacząć? Nie wiesz co robić? Jak się przygotować?
A może już trochę programujesz, znasz jakieś algorytmy, ale nie wiesz czy to wystarczy?

Mierzymy dalej!
Ten tutorial jest dla Ciebie!
Poprowadzi Cię od samego początku – od pierwszego programu do osoby która nie tylko będzie mocno walczyć w OIJ / OI, ale w przyszłości rozwiąże problemy tego świata!
Tu znajdziesz całość materiału – krok po kroku – jak przygotować się do Olimpiady Informatycznej Szkół Podstawowych (OIJ) oraz Licealistów (OI).
Zadania, wytłumaczenie, wzorcowy kod.
Także informacje jak się uczyć.

Warto w grupie
Zachęcam także do bezpłatnych zajęć na żywo, online, dostępnych dla każdego:
https://oki.org.pl/harmonogram-zajec/
Uczestnicząc w zajęciach na żywo, mając nauczyciela który prowadzi, któremu można zadać pytanie, będąc także w grupie w której można porozmawiać – daje to żywą naukę, wspólnotę, wzajemną motywację. Zajęcia na żywo to też cotygodniowe quizy i challenge – dużo łatwiej o systematyczność!

Ile potrzebuję czasu by przygotować się do Olimpiady?
Pierwsze efekty zobaczysz po około 6. Poczujesz, że rozumiesz zadania, wiesz jak je zaatakować, choć jeszcze nie zawsze wszystko wychodzi.
Średnio zajmuje około 1 roku by opanować wiedzę potrzebną do Olimpiady Informatycznej Juniorów i około 2 lat by opanować wiedzę potrzebną do Olimpiady Informatycznej Licealistów. Wiele osób zaczynając we wrześniu i robiąc 4-7 zadań tygodniowo jest w stanie w tym samym roku dostać się do III etapu OIJ, uzyskać tytuł finalisty czy laureata.
Ale można szybciej. W miesiąc opanować programowanie. W kolejny miesiąc podstawowe techniki, podejścia algorytmiczne. Po prostu więcej musisz poświęcić więcej czasu na robienie zadań, poznawanie algorytmów, własne myślenie.

Jakie tempo?
Rekomenduję robienie 3-4 zadań tygodniowo. Pamiętaj, że musisz mieć czas na odpoczynek, spotkania, rower.
* Ważne by w każdym tygodniu robić 3-4 zadania. By czas nie prześlizgiwał się między palcami, by nie odkładać, nie przekładać.
* Każde zadanie to 2h do 12h czasu – musisz mieć odpowiednią ilość czasu tygodniowo
* Być może zaplanuj z góry w jakie dni, ile czasu poświęcisz na zadania.
* Pamiętaj by siadając do zadania mieć co najmniej 2h ciągłego czasu przed sobą gdy możesz się skupić. To minimalny czas w którym możesz coś zrobić – myśleć, pisać, czy też szukać w Internecie. Możesz również myśleć nad zadaniem w autobusie, przed snem, na spacerze. Ale pamiętaj, że kodowanie czy szukanie wyjaśnień w Internecie wymaga miejsca, komputera, czasu.
* Wykorzystaj weekendy, ferie, wakacje. To czas luźniejszy, bez presji jutra. To dni, gdy możesz spokojnie poświęcić 4h – 6h czystego czasu na zadania. Idealnie między 8:00 – 14:00.
* Staraj się uczyć rano. Wieczorem każdy jest bardziej zmęczony.
* Pamiętaj, że musisz mieć czas na spotkania, rower, nudę. Ale raczej przeznacz na to popołudnia, wieczory. Ranki, południe, czy czas po szkole w środku tygodnia to zadania, rozwój.
* Dlaczego każde zadanie wymaga 2h do 12h?
Praktycznie każde zadanie to coś nowego, coś co zmusza Twój mózg do rozwoju. Każdy problem to nowe podejście algorytmiczne które układasz sobie w głowie lub pomysł na który trzeba wpaść czy też nowe elementy w programowaniu, które trzeba poćwiczyć. To wszystko wymaga, czasu, przemyślenia, spokoju. Od każdego. Być może wpadniesz na pomysł i zakodujesz od razu a być może zadanie zajmie Ci wiele godzin – myślenie nad problemem, będziesz potrzebował analizować rozwiązanie czy też długimi godzinami będziesz znajdował błąd (debugował).

Czy warto?
Poświęcę tak dużo czasu. Czy warto?
Wchodzisz w przygodę która wykracza daleko poza Olimpiadę. Jej celem jest robienie w życiu tego co kochamy, pomaganie, pokonywanie problemów. Dziś rozpoczynasz piękną podróż. Podróż, która prowadzi do rozwiązywania największych problemów jakie mamy jako ludzie, do własnego start-upu czy udziału w fascynujących projektach. Nie wierzysz? Ci którzy przed Tobą zaczęli ta podróż publikują prace naukowe, kontrolują loty rakiet, są w ośrodkach badawczych Microsoft, Google, … Oni maja taki sam mózg jak Ty. I kiedyś – tak jak Ty, nie potrafili napisać programu “Hello world” czy rozwiązać najprostszego zadania z Olimpiady. Jak to się stało, że przeżyli piękną przygodę Olimpiady? Jak to się stało, że są w takim miejsc? Po prostu robili zadania. Tylko tyle? Aż tyle! Codziennie, w każdym tygodniu robili zadania. Po kolei, od najprostszych do coraz trudniejszych. Każdego dnia mały kroczek, każdego dnia mocniejsi. Poświęcili się swojej pasji, uwierzyli, weszli w najpiękniejszą przygodę życia.
Zaufaj swojemu mózgowi. On jest mocny. Warto go rozwijać.
Nadaj swoim działaniom cel i sens. Dziś Olimpiada, jutro najciekawsze problemy świata, firm.
Uwierz, że możesz. Niech każde zrobione zadanie będzie wielką radością. Motywacją by robić kolejne, trudniejsze.
Nie porównuj się do innych – to do niczego nie prowadzi – każde dnia mocniejsi to wystarczy
W czasie tej podróży pokonasz szczyty, spotkasz niesamowitych ludzi, doświadczysz radości. Ale też będzie czekał Cię wysiłek, zmęczenie, pot. Tak jak na wycieczce rowerowej. Jednak każde rozwiązane zadanie, etap Olimpiady który uda się pokonać wynagrodzą stokrotnie ten wysiłek. Tak jak widok ze zdobytej góry. Życzę Ci pięknego widoku!

Dlaczego algorytmika jest najbardziej fascynująca dziedziną?
Wyobraź sobie, że chcesz znaleźć lek na pewną chorobę. Co trzeba zrobić?:
1. Wytypować najbardziej obiecuje składniki i sposób ich połączenia
2. Sprawdzić czy działają
3. Zmieścić się z powyższym w sensownym czasie.
Niestety jest to nierealne. Sprawdzenie najszybszym komputerom wszystkich potencjalnych związków chemicznych czy są w stanie pomóc w chorobie zajmie miliony, miliardy lat. Podobnie jest w każdej możliwej dziedzinie: w wyborze strategii inwestycyjnych, rozszyfrowywaniu starożytnych pism czy zwykłym układaniu planu szkolnego.

W każdej dziedzinie chcemy znaleźć najlepsze rozwiązanie: ekologiczny plastik, miejsce na wybudowanie sklepu, czy cokolwiek innego. I żeby to zrobić potrzeba sprawdzić ogromną ilość możliwości. Tak ogromną, że najszybszym komputerom zajmie to miliony lat.

I tu wchodzisz Ty. Mówisz komputerowi:
Hej komputerze! Nie ma sensu tyle się męczyć! Nie ma sensu sprawdzać wszystkiego. Wiele rzeczy powtarzasz – szkoda czasu… Można do tego podejść inaczej.
I komputer nie będzie już znajdował leku miliony lat. Zrobi to w rok, godzinę a może sekundę!

To coś bardziej wspaniałego niż czary. To moment który Ci życzę. To cel naszej podróży. To góra na którą się wspinamy, która da nam niesamowitą radość, piękny widok dookoła.

Olimpiada jest tylko środkiem który Cię przygotowuje do tej podróży. Jest motywatorem byś poznał metody, podejścia, pomysły. Nie ważne jak Ci pójdzie na Olimpiadzie. Liczy się jak głęboko poznasz poszczególne dziedziny, czy je zrozumiesz, jak swobodnie będziesz się nimi posługiwać. Bo w przyszłości to co poznasz, zrozumiesz, sam odkryjesz posłuży Ci do tego byś był magikiem – sprawił, że coś co zajmuje miliony wykona się w sekundę. Gry przestaną się zacinać, strony będą się szybciej otwierać, założysz firmę która przebije Google’a!

Ale jak to? Ja dziś nie umiem napisać nawet linijki kodu?
Pamiętaj o naszych zasadach:
a. 3-4 zadania tygodniowo
b. minimum 2h do4h samodzielnego myślenia nad zadaniem
c. zaglądamy do rozwiązania na dowolnie długo ale nie więcej niż raz
d.  materiał jest opanowany gdy rozwiązujemy problemy bez zaglądania do odpowiedzi
e. dajmy sobie 6 miesięcy na pierwsze efekty…

Jak ja będę rozwiązywał problemy?

Chciałbym więcej zadań robić niż w tym tutorialu. Gdzie znajdę zadania?
Wejdź na stronę:
https://oki.org.pl/lista-zadan-materialy.php
Znajdziesz tam setki zadań które możesz sortować i wyszukiwać po poziomie trudności, wymaganej wiedzy (kliknij “Pokaż dodatkowe informacje w tabeli”) . Ostatnia kolumna to link do omówienia i kodu.

=
Programowanie
Rekomenduje naukę i wykorzystanie języka C++

  • Używany na wszystkich konkursach – Olimpiady: polska, amerykańska, międzynarodowe , Wszystkie konkursy informatyczne
    Co do pozostałych języków nie ma takich gwarancji
  • Najlepiej pozwala zapisać nasze pomysły algorytmiczne
  • Najszybszy

No i pozwala zrozumieć jak działa nasz komputer. A to powoduje, że reszta staje się prosta…

Co muszę umieć z języka C++ by startować w Olimpiadzie Informatycznej / Olimpiadzie Informatycznej Juniorów?
Rekomenduje byś poznał pełna wersję. Ale by wystartować w Olimpiadzie wystarczy:

  • Wypisywanie (cout)
  • Wczytywanie (cin)
  • Warunek (if)
  • Pętla (for)
  • Funkcje
  • Tablice

Niezależnie rekomenduję przejście całego kursu C++.  Aż do zasad czystego kodu.
Dlaczego?

  • Będziesz pisać kod bez błędów.
  • Pisanie kodu na konkursie zajmie Ci mniej czasu
  • Będziesz mieć radość z programowania!

=
Programowanie

1. Pierwszy program – wypisujemy dane na ekran
Zadania z pełnym omówieniem i kodem:
1A. Zadanie Serce – rysunek serca na ekranie
https://szkopul.edu.pl/problemset/problem/serce/site
Omówienie: https://youtu.be/zN3CApegsSY?t=1682
Kod / linki / rozwiązanie: https://oki.org.pl/serce/

1B. Zadanie Choinka – rysunek choinki na ekranie
https://szkopul.edu.pl/problemset/problem/byKw2vwQV3stdD_23STSTQVq/site
Omówienie: https://youtu.be/xF5wlR-xX8g?t=2072
Kod / linki / rozwiązanie: https://oki.org.pl/choinka/

1C. Zadanie Buźka – rysunek pyska tygrysa na ekranie
https://szkopul.edu.pl/problemset/problem/buzka/site
Omówienie: https://youtu.be/SfZS7r0ebGQ?t=2604
Kod / linki / rozwiązanie: https://oki.org.pl/buzka/

Pozostałe zadania:
1D. Zadanie LOVE – rysunek tekstu LOVE złożonego z gwiazdek
https://szkopul.edu.pl/problemset/problem/love/site


2. Wczytywanie danych, Zmienne
2A. Domino piling – musimy określić ile maksymalnie kostek domina możemy umieścić na planszy
https://codeforces.com/problemset/problem/50/A
Omówienie: https://youtu.be/Fe1SjCbc5iA?t=4973
Kod / linki / rozwiązanie: https://oki.org.pl/domino-piling/


3. Warunek, podejmowanie decyzji, if
3A

Pozostałe zadania:
3B. Zagadka – trzeba rozwiązać równanie i sprawdzić czy wynik jest liczbą całkowitą
https://turnieje.solve.edu.pl/tasks/view/154
Podpowiedź: https://oki.org.pl/lista-zadan-materialy.php

4. Pętla for
Crosswords
http://usaco.org/index.php?page=viewproblem2&cpid=488
Trudniejsze na pętle – przejście po planszy.
Marathon (USACO / Bronze)
http://usaco.org/index.php?page=viewproblem2&cpid=487
Proste do zakodowania ale minimalnie algorytmiczne. Wymaga prostego pomysłu. Wejście w algorytmikę.

 

=
Rozwiązywanie problemów, Olimpiada, Algorytmika
Zakładam, że umiesz programować. W C++ (preferowane) lub Python. Jeśli nie – zachęcam do lekcji powyżej.
Poniżej zbiór problemów wymaganych podczas OIJ oraz OI wraz ze szczegółowymi omówieniami.
Pamiętaj, by najpierw pomyśleć samemu pomyśleć min 4h: https://youtu.be/QgLyXYmFQeU?t=2019
I nie zaglądać do rozwiązania więcej niż raz: https://youtu.be/pkLXuuOe_qA?t=3625

1. Pomysł
By startować w Olimpiadzie Informatycznej / Olimpiadzie Informatycznej Juniorów nie potrzeba gigantycznej wiedzy. Często nie potrzeba żadnej wiedzy. Wystarczy prosty pomysł, obserwacja…
Rekomenduję – na początek przygody z Olimpiadą – następujące zadania wymagające jedynie umiejętności programowania i prostego pomysłu.

1A. Bankiet (II etap Olimpiady Informatycznej Juniorów)
https://szkopul.edu.pl/problemset/problem/NQamRQ2UZEwn6gPqo-l6nat9/site
Omówienie: https://youtu.be/VFJF24BRTyo?t=1365
Kod / linki / rozwiązanie: https://oki.org.pl/bankiet/
Zadanie z prostym pomysłem. Tomek dodatkowo pokazuje czym jest złożoność: https://youtu.be/VFJF24BRTyo?t=3915
Analogiczne: Bankiet, Dance Mooves, Dwukrotność sumy cyfr

1B. Swapity Swapity Swap (USACO Silver)
http://www.usaco.org/index.php?page=viewproblem2&cpid=1014
Omówienie: https://youtu.be/nvA92I5nU0c?t=1480
Kod / linki / rozwiązanie: https://oki.org.pl/swapity-swapity-swap/
Dość trudne zadanie związane z cyklami. W pewnym sensie rozwinięcie zadania Bankiet. Ale warto pomyśleć, zaatakować. Jeśli się nie uda to normalne – warto posłuchać rozwiązania i samemu zrobić. To poziom finału OIJ, czy też I-etapu OI-a.
Analogiczne: Bankiet, Dance Mooves, Dwukrotność sumy cyfr

1C. Pyramid of Glasses (Codeforces Div.2 / B)
Omówienie: https://youtu.be/hVH-4EDGI6w?t=1310
Kod / linki / rozwiązanie: https://oki.org.pl/pyramid-of-glasses/
Symulacja przelewania się wody w szklankach.

Pozostałe zadania:
1D. Marathon (USACO / Bronze)
http://usaco.org/index.php?page=viewproblem2&cpid=487
Bardzo proste zadanie z minimalną algorytmiką.

1D. Awantura o Czapki (Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym)
https://szkopul.edu.pl/c/testa2/problemset/problem/czapki/site
Rozwiązanie: https://oki.org.pl/awantura-o-czapki/
Bardzo proste zadanie z jedną obserwacją i banalnym do napisania kodem.

1E. Pionki (finał Olimpiady Informatycznej Juniorów)
https://szkopul.edu.pl/problemset/problem/ZhrqkG9W7TYF2VPrIuR1Ufry/site
Rozwiązanie: https://oki.org.pl/pionki/
Zadanie z finału Olimpiady Informatycznej Juniorów. Tym niemniej niesamowicie proste.

1F. Śpiew (I etap Olimpiady Informatycznej Juniorów)
https://szkopul.edu.pl/problemset/problem/JDLRIKmmfMWZ7G1Sy6Ldq7m8/site
Podpowiedź: https://oki.org.pl/lista-zadan-materialy.php

1G. Chess Tournament (Codeforces Div.2 / B)
https://codeforces.com/contest/1569/problem/B
Podpowiedź: https://oki.org.pl/lista-zadan-materialy.php

2. NWD / GCD – Największy Wspólny Dzielnik
W literaturze angielskojęzycznej to GCDGgreatest Common Divisor. I tak te zadania są oznaczone na stronie: https://oki.org.pl/lista-zadan-materialy.php

Bardzo często pojawiająca się technika i bardzo prosta. Kod NWD to dosłownie 3 linijki. A rozwiązuję dziesiątki problemów.

Polecam jako startowe:
1a. Trening Centaura (dodać do https://oki.org.pl/lista-zadan-materialy.php):
https://szkopul.edu.pl/problemset/problem/tcz/site/
Zadanie z I etapu IX OIG — zawodów drużynowych: https://youtu.be/I3woOiIWHjg

3. Kombinatoryka

Zadania z kombinatoryki pojawiają się zarówno na Olimpiadzie Informatycznej Juniorów jak też Licealistów.

3a. Impreza krasnali
Średnie zadanie kombinatoryczne. Spokojnie do zrobienia dla każdego. Wymaga namysłu, rozrysowania, obserwacji. Dość proste do wytłumaczenia.
https://sio2.mimuw.edu.pl/c/oi29-1/p/imp/