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ść!

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.

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ł).

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!

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.

=

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 – Lista zagadnień

Pętla: https://oki.org.pl/tutorial#petla
Pętla: https://oki.org.pl/tutorial#petla-zadania
Funkcje: https://oki.org.pl/tutorial#funkcje
Sortowanie według własnych kryteriów: https://oki.org.pl/tutorial#sortowanie-wlasne
struct – własny typ danych: https://oki.org.pl/tutorial#struct
set – linki do omówień: https://oki.org.pl/tutorial#set
set – lista zadań: https://oki.org.pl/tutorial#set-lista-zadan
map – linki do omówień: https://oki.org.pl/tutorial#map
map – lista zadań: https://oki.org.pl/tutorial#map-lista-zadan
Operacje bitowe: https://oki.org.pl/tutorial#operacje-bitowe
Lista zagadnień – Programowanie C++: https://oki.org.pl/tutorial#programowanie-lista-zagadnien

Pierwszy program – wypisujemy dane na ekran

Wypisywanie znaków specjalnych – ” \ – https://youtu.be/H9dRa-1vX4o?t=820

Zadania z pełnym omówieniem i kodem:
1. Auto – rysujemy samochód który składa się z 3 linijek:
https://szkopul.edu.pl/problemset/problem/auto/site
Omówienie: https://youtu.be/-_Yplxdir8s?t=1711
Kod / linki / rozwiązanie: https://oki.org.pl/auto/

2. 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/

3. 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/

4. 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/

Pozostałe zadania:

6. “Hello world!” – wypisać tekst “Hello world” na ekranie:
https://szkopul.edu.pl/problemset/problem/hlw/site/

7.  LOVE – rysunek tekstu LOVE złożonego z gwiazdek
https://szkopul.edu.pl/problemset/problem/love/site

8. Cieżarówka – piękny rysunek cięzarówki dla brata!
https://szkopul.edu.pl/problemset/problem/czr/site

9. Kostka Rubika – aż się chce uładać po narysowaniu!
https://szkopul.edu.pl/problemset/problem/koru/site

10. Milczenie – mini wierszyk o szkole do wypisania na ekranie
https://szkopul.edu.pl/problemset/problem/mil/site

11. Tłum – jednolinjkowy rysunek ASCII do narysowania
https://szkopul.edu.pl/problemset/problem/tlm/site 

12. Kaczka dziwaczka – Brzechwa na ekranie! – 3 linijki do wypisania
https://szkopul.edu.pl/problemset/problem/kca/site

13. Gwiazdki – narysować 6 gwiazdek które formują trójką
https://szkopul.edu.pl/problemset/problem/4KQzy7thNGbDojJPuUJakZ8e/site

–
2. Wczytywanie danych, Zmienne

Dokładne od początku wytłumaczenie long long: https://youtu.be/B0bUvGFdgGA?t=2223

Krótkie wytłumaczenie long long vs int: https://youtu.be/H1kz3u9zIWg?t=2290
– long long może trzymać 1 i 18 zer
– int może trzymać 1 i 18 zer
Czy zawsze opłaca się long long? https://youtu.be/H1kz3u9zIWg?t=2391
– long long jest wolniejszy
– potrzebuje więcej pamięci

1. Zadanie Read/Write 1 – ćwiczeniowe
https://szkopul.edu.pl/problemset/problem/VYKVdv984yra7FZWHFpzfy6j/site
wczytać 3 liczby i wypisać je w kolejności zwykłej i odwrotnej 

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

Dokładne omówienie warunku: https://youtu.be/H9dRa-1vX4o?t=1832
– kahoot:
– omówienie całego kodu cpp.sh
– od warunku zależy jedna insttrukcja

== vs = czyli pojedyczne równa się vs podwójne: https://youtu.be/H9dRa-1vX4o?t=3332
– Najczęstszy błąd

Wcięcia bez znaczenia dla C++: https://youtu.be/H9dRa-1vX4o?t=2009
– od warunku zależy jedna instrukcja

Klamry w warunku: https://youtu.be/H9dRa-1vX4o?t=2137
– Klamra – jedna instrukcja złożona:

Omówienie konstrukcji if / return: https://youtu.be/H9dRa-1vX4o?t=2316

Wielokrotne konstrukcje if / return: https://youtu.be/H9dRa-1vX4o?t=2572

Konstrukcja if / else if: https://youtu.be/H9dRa-1vX4o?t=2884
– alternatywa dla if / return

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

Ciasto
https://szkopul.edu.pl/problemset/problem/cia/site
Bardzo sympatyczne zadanie wymagające tylko użycia warunku.
Zadanie ułożone przez Wiktora Gatnera w ramach konkursu OKI Wakacje 2023.

 

Pętla – lista zagadnień
Wczytywanie i porównywanie znaków w pętli:
https://youtu.be/aEJZmFVTgfw?t=1578

 

 

Pętla – lista zadań

Bucket Brigade – podwójna pętla, oczywiste logicznie, trochę kodu, zliczyć pola by przejśc bez wiadra
https://szkopul.edu.pl/problemset/problem/QqrIVPb5cf4HtN0IpXw5HowF/site
Omówienie: https://youtu.be/ZkewY7oUw0Y?t=1261
Kod / linki / rozwiązanie: https://oki.org.pl/pomiary

 

Pętla while – lista zadań

Pomiary
https://szkopul.edu.pl/problemset/problem/QqrIVPb5cf4HtN0IpXw5HowF/site
Omówienie: https://youtu.be/ZkewY7oUw0Y?t=1261
Kod / linki / rozwiązanie: https://oki.org.pl/pomiary

Potęgi dwójki – wypisać potęgi dwójki do podanego n
https://szkopul.edu.pl/problemset/problem/LIByQN4dThAGhaebi6DEQpyz/site

Dwójki – Ile jest potęg dwójki mniejszych od n
https://szkopul.edu.pl/problemset/problem/hnqWjOVNGN2AM3769svlTYv3/site

 

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ę.

5. Tablice
Całościowe wyjaśnienie tablic v1:
https://youtu.be/IxwQcOkKY30?t=1965
– od samego wejścia do online’owego kompilatora C++ ideone
– pokazanie problemów ze zmiennymi
– dokładne omówienie tablic

Całościowe wyjaśnienie tablic v2:
https://youtu.be/q92kykzx1Vw?t=847
– tablica 3 temperatur
– wypisywanie

Funkcje

Dlaczego powinniśmy stosować własne funkcje?
https://youtu.be/IlhF2UGjJRU?t=117

 

 

Liczby rzeczywiste – zadania

 

 

Sortowanie według własnych kryteriów

Gdzie wykorzystujemy własne sortowanie?
https://youtu.be/IlhF2UGjJRU?t=9

Omówienie własnego sortowania:
https://youtu.be/DZg-nxee2Lk?t=5991

 

Struct – własny typ danych

Struct pełne wyjaśnienie od początku, kiedy wykorzystujemy
– przykład z piosenkami
https://youtu.be/IlhF2UGjJRU?t=905

 

Set – tablica bez indeksów

Gdzie przydaje się set? – Plagiaty i informatyka
https://youtu.be/nPIewnyLFMk?t=15

Czym jest set?
https://youtu.be/JcyOLsAoL3w?t=35

Pełne od podstaw omówienia set – od omówienia ideone:
https://youtu.be/JcyOLsAoL3w?t=597 

O co chodzi w set? Pełne omówienie od początku
https://youtu.be/JcyOLsAoL3w?t=655

Insert – dodawanie elementów do set:
https://youtu.be/JcyOLsAoL3w?t=928 

Wskaźnik / iterator w set:
https://youtu.be/JcyOLsAoL3w?t=1432

Wypisywanie elementów w set:
https://youtu.be/JcyOLsAoL3w?t=1432

lower_bound, upper_bound – doładne wyjaśnienie:
https://youtu.be/JcyOLsAoL3w?t=4349

lower_bound, upper_bound w kahoot:
https://youtu.be/nPIewnyLFMk?t=682

set z własnym porządkiem – własna funkcja porządkująca set
https://youtu.be/nPIewnyLFMk?t=5007

set z własnym porządkiem – kahoot
https://youtu.be/nPIewnyLFMk?t=6215

 

Set – lista zadań

Wypisz liczby 2
https://szkopul.edu.pl/problemset/problem/wl2/site/
Omówienie: https://youtu.be/JcyOLsAoL3w?t=4979
Kod / linki / rozwiązanie: https://oki.org.pl/wypisz-liczby-2/

Antyplagiat-1
https://szkopul.edu.pl/problemset/problem/ap1/site
Omówienie: https://youtu.be/nPIewnyLFMk?t=1725
Kod / linki / rozwiązanie: https://oki.org.pl/antyplagiat-1/

 

map – super tablica

map – wyjaśnienie od początku:
https://youtu.be/gnHaRSZ1tIo?t=717

Jak przejść po map?
https://youtu.be/gnHaRSZ1tIo?t=4640

Znajdowanie elementu najbliższego w map:
https://youtu.be/gnHaRSZ1tIo?t=5360

 

map – Lista zadań

Wycinek
https://szkopul.edu.pl/problemset/problem/pAy3KzzMQ8Gh-LFsyL0tZts6/site
Zadanie wymagające minimalnego pomysłu, już zadanie Olimpijskie.
Rozwiązanie da Ci satysfakcję – to sztandarowe zadanie wszystkich rozmów rekrutacyjnych do gigantów takich Facebook, Google. To także zadanie, jakie może spokojnie pojawić się na II etapie OIJ albo jako element zadania OI.

Świąteczne patyczki
https://szkopul.edu.pl/problemset/problem/pAy3KzzMQ8Gh-LFsyL0tZts6/site
Ile jest liczb które spełniają a^2 + b^2 = c^2.
Tworzymy map *tablica nie da rady) ile jest wystąpień każdej liczby^2
Dla każdej dwójki a,b sprawdzam ile jest c^2 wystąpień

 

Operacje bitowe

Po co nam liczby dwójkowe?
– komputer trzyma liczby dwójkowo!
https://youtu.be/qm1NLg4QOmM?t=1196

Operacja logiczna AND:
– dokładne wytłumaczenie
https://youtu.be/qm1NLg4QOmM?t=4887

Zadania:
Różnica bitów: https://szkopul.edu.pl/problemset/problem/bibi/site
– wypisać różnicę bitów na pozycjach i/j.

 

=
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

 

Algorytmika – Lista zagadnień
Grafy: https://oki.org.pl/tutorial#2pointers-zadania
Grafy: https://oki.org.pl/tutorial#grafy
DFS: https://oki.org.pl/tutorial#dfs
Find And Union: https://oki.org.pl/tutorial#fau

 

Lista zagadnień – Algorytmika: https://oki.org.pl/tutorial#algorytmika-lista-zagadnien

 

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. Sumy prefiksowe

Interesting drink / Codeforces / Div2 / B
– Oczywiste na Binary Search
– Sumy prefiksowe
Jeśli można biezemy sumy prefiksowe – bez long, trochę szybciej
https://codeforces.com/problemset/problem/706/B/

 

2. NWD / GCD – Największy Wspólny Dzielnik
W literaturze angielskojęzycznej to GCD – Ggreatest 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

Interesting drink / Codeforces / Div2 / B
– Oczywiste na Binary Search
– Sumy prefiksowe
Jeśli można bierzemy sumy prefiksowe – bez long, trochę szybciej
https://codeforces.com/problemset/problem/706/B/

3. Binary Search po wyniku

K-th Not Divisible by n / Codeforces
Idealne na początek Binary Search po wyniku
Znaleźć k-tą liczbą nie dzieląca się przez n.
Można Binary Search po wyniku można w czasie stałym.
https://szkopul.edu.pl/problemset/problem/idOsQqZfghtFYro_Ymuq-USF/site

SQUFOF
Idealne zadanie na początek Binary Search po wyniku.
https://szkopul.edu.pl/problemset/problem/fof/site
Omówienie: https://youtu.be/pzPACXcSuss?t=1755
Kod / linki / rozwiązanie: https://oki.org.pl/squfof/

K-th Not Divisible by n / Codeforces / Div2 / B
– czas stały lub Binary Search
https://codeforces.com/problemset/problem/1352/C

3. 2-pointers

Kefa and Company / Codeforces / Div2 / B
https://codeforces.com/problemset/problem/580/B

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/

 

Sumy prefiksowe

Sumy prefiksowe polegają na obliczaniu sumy wartości kolejnych elementów tablicy. Przykładowo dla tablicy liczb [2, 4, 6, 8] suma prefiksowa wynosi [2, 6, 12, 20]. Obliczanie sum prefiksowych może być przydatne w wielu algorytmach, szczególnie kiedy potrzebujemy szybkiego dostępu do sumy elementów w danym przedziale. Dzięki wykorzystaniu sum prefiksowych można uniknąć powtarzających się obliczeń i zredukować czas wykonywania programu.

Binary Search

Binary search to algorytm, który błyskawicznie znajduje element w posortowanej tablicy. Podczas szukania zadanej wartości sprawdza element środkowy i odrzuca tą połowę gdzie na pewno nie ma szukanej wartości. Powtarza te czynności aż znajdzie żądany element.
Pesymistycznie wykona log2(n) operacji – czyli by znaleźć wartość w tablicy o bilionie (10^12) elementów będzie potrzebował maksymalnie 40 operacji gdyż log2(10^12) to około 40 albo inaczej 2^40 to około 10^12.

Szybki Algorytm Euklidesa

Głównym celem algorytmu Euklidesa jest znalezienie NWD dwóch liczb. Algorytm ten polega na wielokrotnym dzieleniu jednej liczby przez drugą i zamiany wartości liczby większej na liczbę mniejszą, a resztę z dzielenia na mniejszą liczbę, aż zostanie osiągnięta reszta równa zero. Na przykład dla liczb 100 i 36 NWD(100,36) wynosi 4 gdyż:
100%36=2 r 28         36%28= 1 r 8            28%8=3 r 4           8%4=2 r 0      Koniec gdyż r=0
Ostatnie dzielnik to 4 (gdy reszta 0) więc 4 jest NWD (100,36)
Autor: Dawid Gójski

 

Grafy

Gdzie wykorzystuje się grafy?
https://youtu.be/dFKlYmMg6UY?t=46

Pełne omówienie grafów, kod wczytania i wypisania grafu:
https://youtu.be/dFKlYmMg6UY?t=1615

Quiz z omówieniem grafu
– czym jest graf
– kod
https://youtu.be/H8fWSWqe2m4?t=735

Czym jest drzewo :
https://youtu.be/H8fWSWqe2m4?t=5144

 

DFS

Algorytm DFS – dokładne omówienie:
https://youtu.be/H8fWSWqe2m4?t=3654

Implementacja DFS:
https://youtu.be/H8fWSWqe2m4?t=5058

Złożoność DFS-a
https://youtu.be/H8fWSWqe2m4?t=4920

Wytłumaczenie DFS-a w quizie Kahoot:
https://youtu.be/H8fWSWqe2m4?t=6605

 

Find And Union

Find And Union – wytłumaczenie FIND w kahoot:
https://youtu.be/MiuWOJ74EHw?t=745

Find And Union – wytłumaczenie UNION w kahoot:
https://youtu.be/MiuWOJ74EHw?t=5872

 

 

Omówienia zadań – Zajęcia Olimpijskiego Koła Informatycznego

Tydzień 1 – 2023/24

Kaczka Dziwaczka: https://youtu.be/WGI1XTV-cb4?t=727
Programowanie OD PODSTAW, Pierwszy program, Narysować kaczkę na ekranie
Treść zadania Kaczka Dziwaczka: https://szkopul.edu.pl/problemset/problem/kca/site
Źródło: OKI
Kod / rozwiążanie: https://oki.org.pl/kaczka-dziwaczka/

Ntarsis’ Set: https://youtu.be/3KYBBeq8SfM?t=291
Olimpiada Poziom II, Binary Search po wyniku
Treść zadania Ntarsis’ Set: https://codeforces.com/contest/1853/problem/C
Źródło: Codeforces / Div2 / Poziom C.

Max Median: https://youtu.be/3KYBBeq8SfM?t=2789
Olimpiada Poziom II, Binary Search po wyniku
Treść zadania Ntarsis’ Set: https://codeforces.com/contest/1853/problem/C
Źródło: Codeforces / Div2 / Poziom D.

 

Max Median / Div2

a