Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Ten odcinek omawia dokładnie ten temat.
Co już umiesz i czego się nauczysz
Ta lekcja otwiera trzeci etap kursu i zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair, Vector, Sortowanie, Max / Min, Zaokrąglanie, Silnia i Wartość bezwzględna.
Szybkość programów już kilka razy pojawiła się w kursie. W lekcji o pętli for poznałeś regułę „około 100 milionów obrotów na sekundę” i pętlę do pierwiastka. W lekcji o while liczyłeś, ile razy da się podzielić liczbę przez 2, a w lekcji o modulo — potęgowałeś szybko. W lekcji o tablicach zliczałeś wystąpienia i przesiewałeś liczby pierwsze sitem, w lekcji o vectorze liczyłeś sumy prefiksowe i chodziłeś dwoma wskaźnikami, a w lekcji o sortowaniu porównałeś dwie pętle z sort i szukałeś przez lower_bound. Każdy z tych pomysłów pojawił się osobno, przy okazji.
Teraz złożymy je w jedną całość. Nauczysz się liczyć, ile pracy wykonuje program, nazywać to krótko notacją O, szacować, czy zdąży w limicie czasu, i wybierać szybszy pomysł, gdy pierwszy jest za wolny. Uczymy się tak samo jak poprzednio: przepisuj przykłady, licz obroty na kartce, zanim klikniesz „Pokaż odpowiedź”, i rób ćwiczenia po każdej części.
Liczymy obroty
Pojedyncza pętla, pętle jedna po drugiej, pętla w pętli i trójkąty, a potem pętle, które dzielą: logarytm i zgadywanie liczby.
Notacja O i czas
O(1), O(log n), O(n), O(n log n), O(n²)… ukryte koszty, reguła 10⁸ na sekundę, ograniczenia z treści i dane z generatora.
Szybciej: wzory i tablice
Wzór zamiast pętli, pierwiastek zamiast n, sumy prefiksowe, tablice zliczeń, sito i tablica różnic.
Sortuj i szukaj
Sortowanie raz, a potem lower_bound w O(log n), dwa wskaźniki i wyszukiwanie binarne po odpowiedzi.
Mapa lekcji
Ile razy wykona się pętla?
Zacznijmy od dwóch programów, które wyglądają prawie tak samo. Oba liczą coś w pętli dla n = 100 000. Pierwszy ma jedną pętlę, drugi — pętlę w pętli.
long long n = 100000, ile = 0;
for (long long i = 1; i <= n; i++) {
ile++;
}
cout << ile << "\n";
long long n = 100000, ile = 0;
for (long long i = 1; i <= n; i++) {
for (long long j = 1; j <= n; j++) {
ile += j % 7; // jakaś praca w środku
}
}
cout << ile << "\n";
Lewy program kończy się, zanim zdążysz mrugnąć. Prawy — gdybyś go uruchomił — liczyłby kilkanaście sekund. Skąd taka różnica? Lewy wykonuje 100 tysięcy obrotów pętli. Prawy: dla każdego z 100 tysięcy obrotów zewnętrznej pętli wewnętrzna robi kolejne 100 tysięcy — razem 10 miliardów. Sto tysięcy razy więcej pracy.
Komputer wykonuje około 100 milionów (10⁸) prostych obrotów pętli na sekundę — znasz tę regułę z lekcji o pętli for. Dla 10 miliardów obrotów to około stu sekund. Dlatego całą lekcję zaczniemy od najprostszej umiejętności: policzyć obroty, zanim uruchomisz program.
Obrót — jednostka pracy
Obrotem nazywamy jedno wykonanie ciała pętli. Nie mierzymy czasu w sekundach, bo zależy od komputera. Liczymy obroty — bo czas jest do nich mniej więcej proporcjonalny: dwa razy więcej obrotów to mniej więcej dwa razy dłużej.
Najpewniejszy sposób, żeby sprawdzić, ile obrotów robi pętla, to wstawić do niej licznik: zmienną, która zwiększa się o 1 w każdym obrocie, i wypisać ją na końcu. Ale licznik działa tylko dla małych danych — dla n = 10¹⁸ program z licznikiem nigdy by się nie skończył. Dlatego nauczymy się liczyć obroty wzorem, prosto z nagłówka pętli.
| nagłówek pętli | ile obrotów | przykład |
|---|---|---|
for (i = 1; i <= n; i++) | n | n = 10 → 10 |
for (i = 0; i < n; i++) | n | n = 10 → 10 (od 0 do 9) |
for (i = n; i >= 1; i--) | n | w dół — tyle samo |
for (i = a; i <= b; i++) | b − a + 1 | od 3 do 7 → 5 |
for (i = a; i < b; i++) | b − a | od 3 do 6 → 4 |
for (i = a; i <= b; i += k) | (b − a) / k + 1 | od 2 do 20 co 3 → 7 |
while (x >= k) x -= k; | x / k | x = 17, k = 5 → 3 |
Od a do b: płot i słupki
Ile jest liczb od 3 do 7? Kusi, żeby odjąć: 7 − 3 = 4. Ale wypiszmy je: 3, 4, 5, 6, 7 — jest ich pięć. To słynny „błąd płotu”: płot długości 4 metrów ze słupkiem co metr ma 5 słupków, bo słupek stoi też na samym początku.
Dlatego pętla for (i = a; i <= b; i++) wykonuje b − a + 1 obrotów. Gdy warunek ma ostre <, ostatnia liczba odpada i zostaje b − a.
A gdy a > b? Warunek jest fałszywy od razu, pętla nie wykona się ani razu — 0 obrotów. Wzór b − a + 1 dałby wtedy liczbę ujemną albo zero, więc ten przypadek trzeba sprawdzić osobno.
long long a, b;
cin >> a >> b;
long long ile = 0;
if (a <= b) ile = b - a + 1;
cout << ile << "\n";
Drugie wejście to dwa tryliony z kawałkiem obrotów. Pętla z licznikiem liczyłaby to setki lat. Wzór odpowiada natychmiast — to pierwszy przykład, w którym zamiast wykonywać pętlę, liczymy, ile razy by się wykonała.
Co k: krok większy niż 1
int a = 2, b = 20, k = 3;
int ile = 0;
for (int i = a; i <= b; i += k) {
cout << i << " ";
ile++;
}
cout << "\n" << ile << " = " << (b - a) / k + 1 << "\n";
Pętla skacze co 3: 2, 5, 8, …, 20. Ile skoków mieści się między a i b? Odległość b − a = 18, a jeden skok ma k = 3, więc skoków jest 18 / 3 = 6. Do tego dochodzi pierwszy obrót (samo a), zanim wykonamy jakikolwiek skok: (b − a) / k + 1 = 7.
Dzielenie jest całkowite. Gdyby b wynosiło 21, skoków dalej byłoby 6 (19 / 3 = 6) — liczba 23 już się nie zmieści. Ostatni odwiedzony to wtedy 20, a nie 21.
Odejmowanie zamiast dzielenia
long long x, k;
cin >> x >> k;
long long ile = 0;
while (x >= k) {
x -= k; // jeden obrót = jedno odejmowanie
ile++;
}
cout << ile << " " << x << "\n";
Ta pętla odejmuje k tak długo, jak się da. Ile razy odejmie? Dokładnie tyle, ile razy k mieści się w x — czyli x / k. A to, co zostanie, to reszta: x % k. Pętla po prostu dzieli z resztą, tylko bardzo powoli.
Dla x = 10¹⁸ i k = 1 wykonałaby 10¹⁸ obrotów. Dzielenie / i % robią to samo w jednym kroku. Zapamiętaj ten wzór myślenia: pętla, która powtarza to samo działanie, często zastępuje jedno sprytniejsze działanie.
Pętle jedna po drugiej: dodajemy
int n = 5, m = 3, ile = 0;
for (int i = 0; i < n; i++) ile++; // n obrotów
for (int j = 0; j < m; j++) ile++; // m obrotów
for (int i = 0; i < n; i++) ile++; // jeszcze n
cout << ile << "\n";
Gdy pętle stoją jedna po drugiej, każda wykonuje się po kolei, w całości, i ich obroty się dodają: n + m + n = 2n + m. Tu 5 + 3 + 5 = 13.
Zupełnie inaczej jest, gdy jedna pętla stoi wewnątrz drugiej — wtedy obroty się mnożą. To temat części 2.
if w pętli nie zmienia liczby obrotów
long long n;
cin >> n;
long long obroty = 0, trzy = 0, piec = 0;
for (long long i = 1; i <= n; i++) {
obroty++;
if (i % 3 == 0) trzy++;
if (i % 5 == 0) piec++;
}
cout << obroty << " " << trzy << " " << piec << "\n";
cout << n << " " << n / 3 << " " << n / 5 << "\n";
Pętla wykonuje n obrotów niezależnie od tego, co jest w środku. if sprawia tylko, że niektóre instrukcje w ciele wykonują się rzadziej: trzy++ co trzeci obrót, czyli n / 3 razy, a piec++ co piąty — n / 5 razy.
Drugi wiersz wyjścia liczy to samo wzorami, bez pętli. Dla n = 100 obie wersje dają to samo. Dla n = 10¹⁸ zdąży tylko druga.
Uwaga: if w pętli zmienia wynik, ale nie oszczędza czasu — sprawdzenie warunku też kosztuje i odbywa się w każdym obrocie.
b − a + 1 (gdy a ≤ b). Co k: (b − a) / k + 1. Pętle jedna po drugiej — obroty się dodają. Instrukcja pod if (i % k == 0) wykonuje się n / k razy. Gdy pętla powtarza odejmowanie albo dodawanie tej samej liczby, zwykle da się ją zastąpić jednym dzieleniem albo mnożeniem.
Najpierw policz obroty w głowie albo na kartce — bez uruchamiania — a dopiero potem kliknij „Pokaż odpowiedź”.
int ile = 0;
for (int i = 5; i <= 12; i++) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 5; i < 12; i++) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 1; i <= 100; i += 10) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 10; i >= 1; i -= 2) ile++;
cout << ile;
Pokaż odpowiedź
int x = 100, ile = 0;
while (x >= 7) { x -= 7; ile++; }
cout << ile << " " << x;
Pokaż odpowiedź
int n = 6, ile = 0;
for (int i = 0; i < n; i++) ile++;
for (int i = 0; i < n; i++) ile++;
for (int i = 0; i < 4; i++) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 1; i <= 30; i++)
if (i % 4 == 0) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 20; i <= 10; i++) ile++;
cout << ile;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Pętla w pętli — obroty się mnożą
Gdy jedna pętla stoi wewnątrz drugiej, wewnętrzna wykonuje się od początku do końca w każdym obrocie zewnętrznej. Jeśli zewnętrzna robi n obrotów, a wewnętrzna m, to ciało wewnętrznej wykona się n razy po m, czyli n · m razy.
Najłatwiej to zobaczyć na kratce: wiersz to obrót zewnętrznej pętli (i), kolumna — obrót wewnętrznej (j). Każde pole (i, j) to jeden obrót ciała. Ile pól, tyle obrotów.
int n = 3, m = 4, ile = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << i * j << " ";
ile++;
}
cout << "\n";
}
cout << "obrotow: " << ile << "\n";
Fragment tabliczki mnożenia: 3 wiersze po 4 liczby. Wewnętrzna pętla (po j) wykonała się 3 razy, za każdym razem w całości — 4 obroty. Razem 3 · 4 = 12.
Gdy obie pętle idą do n, obrotów jest n · n = n² („n kwadrat”). Dla n = 1000 to milion — szybko. Dla n = 100 000 to 10 miliardów — za wolno.
Zapamiętaj zasadę: pętle obok siebie — dodajemy, pętle jedna w drugiej — mnożymy.
Trójkąt: każdy z każdym, ale bez powtórzeń
Na turnieju n zawodników gra każdy z każdym jeden mecz. Ile meczów? Zawodnik 1 gra z 2, 3, …, n; zawodnik 2 — już tylko z 3, …, n (mecz z 1 już był); i tak dalej. W kodzie wewnętrzna pętla zaczyna od i + 1 — jej długość zależy od i. Na kratce zostaje tylko trójkąt nad przekątną.
Przełącz tryby w ramce i przesuwaj n. Obserwuj, ile pól się zapala.
| wewnętrzna pętla | obrotów razem | n = 5 |
|---|---|---|
j = 1 … n | n · n | 25 |
j = i + 1 … n | n · (n − 1) / 2 | 10 |
j = 1 … i | n · (n + 1) / 2 | 15 |
j = 1 … i − 1 | n · (n − 1) / 2 | 10 |
Skąd wzór n · (n − 1) / 2? Pary (i, j) z i < j to wszystkie pola kratki n × n (n² pól) bez przekątnej (n pól), podzielone na pół — bo dokładnie połowa leży nad przekątną. Czyli (n² − n) / 2 = n · (n − 1) / 2.
To samo dostaniesz, dodając długości wierszy: (n − 1) + (n − 2) + … + 1 + 0.
Trójkąt to mniej więcej połowa kwadratu. Dwa razy mniej pracy brzmi dobrze, ale dla dużego n nie ratuje sytuacji: połowa z 10 miliardów to wciąż 5 miliardów.
Suma 1 + 2 + … + n — sztuczka małego Gaussa
long long n;
cin >> n;
long long petla = 0;
for (long long i = 1; i <= n; i++) petla += i;
cout << petla << " " << n * (n + 1) / 2 << "\n";
Schodki „j od 1 do i” to suma 1 + 2 + … + n. Podobno mały Carl Friedrich Gauss policzył ją w szkole w kilka sekund: dodał liczby parami z dwóch końców — 1 + n, 2 + (n − 1), 3 + (n − 2) — każda para daje n + 1, a par jest n / 2. Razem n · (n + 1) / 2.
Program liczy sumę dwa razy: pętlą (n obrotów) i wzorem (jedno działanie). Wyniki są te same, ale wzór działa tak samo szybko dla n = 10 i dla n = 10⁹.
Uwaga na typ: n · (n + 1) dla n = 10⁹ to 10¹⁸ — tylko long long.
Trzy pętle: n³ i trójki
int n = 6;
long long wszystkie = 0, trojki = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++) {
wszystkie++;
if (i < j && j < k) trojki++;
}
cout << wszystkie << " " << trojki << "\n";
cout << n * n * n << " " << n * (n - 1) * (n - 2) / 6 << "\n";
Trzy zagnieżdżone pętle po n to n³ („n do sześcianu”) obrotów: dla n = 6 — 216, dla n = 1000 — miliard (za wolno!), dla n = 500 — 125 milionów (na granicy).
Trójek i < j < k („wybierz 3 z n”, znasz to z lekcji o silni) jest n · (n − 1) · (n − 2) / 6 — mniej więcej n³ / 6. Znowu: stała 1/6 pomaga, ale nie zmienia faktu, że praca rośnie jak n³.
Wewnętrzna pętla o stałej długości
string s = "kot w butach";
int ile = 0;
for (int i = 0; i < (int)s.size(); i++) // n obrotów
for (char z = 'a'; z <= 'z'; z++) // zawsze 26
if (s[i] == z) ile++;
cout << ile << "\n";
Tu wewnętrzna pętla zawsze robi 26 obrotów — tyle, ile liter w alfabecie, niezależnie od długości napisu. Razem 26 · n obrotów.
To wciąż praca rosnąca jak n, a nie jak n²: dwa razy dłuższy napis to dwa razy więcej pracy. Stała 26 sprawia tylko, że program jest 26 razy wolniejszy od jednej pętli — przy 10⁶ znaków to 2,6 · 10⁷ obrotów, czyli nadal szybko. W części 4 nazwiemy takie stałe po imieniu i nauczymy się je pomijać.
n · m obrotów, dla n = m — n². Wewnętrzna od i + 1 do n: n · (n − 1) / 2 (pary bez powtórzeń). Od 1 do i: n · (n + 1) / 2. Trzy pętle po n: n³. Wewnętrzna pętla o stałej długości (26 liter, 10 cyfr) mnoży pracę tylko przez stałą.
Najpierw policz obroty na kartce — narysuj sobie kratkę, jeśli pomaga — a dopiero potem kliknij „Pokaż odpowiedź”.
int ile = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 7; j++) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 0; i < 4; i++) ile++;
for (int j = 0; j < 7; j++) ile++;
cout << ile;
Pokaż odpowiedź
int n = 8, ile = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) ile++;
cout << ile;
Pokaż odpowiedź
int n = 8, ile = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
for (int k = 0; k < 5; k++) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 3; j++) ile++;
for (int k = 0; k < 2; k++) ile++;
}
cout << ile;
Pokaż odpowiedź
long long n = 100000;
cout << n * (n - 1) / 2;
Pokaż odpowiedź
int ile = 0;
for (int i = 1; i <= 6; i++)
for (int j = i; j <= 6; j += 2) ile++;
cout << ile;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Pętle, które dzielą — logarytm
Do tej pory licznik pętli rósł o 1 albo o k. Teraz zajmiemy się pętlami, w których coś jest dzielone na pół (albo podwajane) w każdym obrocie. Takie pętle są niesamowicie szybkie: nawet dla liczby miliardowej wykonują tylko kilkadziesiąt obrotów.
long long n;
cin >> n;
int ile = 0;
while (n > 1) {
n /= 2;
ile++;
}
cout << ile << "\n";
| obrót | n po dzieleniu |
|---|---|
| 1 | 500 |
| 2 | 250 |
| 3 | 125 |
| 4 | 62 |
| 5 | 31 |
| 6 | 15 |
| 7 | 7 |
| 8 | 3 |
| 9 | 1 |
Tysiąc da się podzielić na pół tylko 9 razy, zanim zostanie 1. A trylion (10¹⁸) — tylko 59 razy! To dlatego, że każde dzielenie zabiera połowę tego, co zostało: po 10 dzieleniach zostaje około tysięczna część, po 20 — milionowa, po 30 — miliardowa.
Logarytm — ile razy można podzielić na pół
| n | mniej więcej | log₂ n |
|---|---|---|
| 2¹⁰ = 1024 | tysiąc (10³) | 10 |
| 2²⁰ = 1 048 576 | milion (10⁶) | 20 |
| 2³⁰ = 1 073 741 824 | miliard (10⁹) | 30 |
| 2⁴⁰ | bilion (10¹²) | 40 |
| 2⁶⁰ | trylion (10¹⁸) | 60 |
Liczbę, która mówi, ile razy trzeba podzielić n przez 2, żeby dojść do 1, nazywamy logarytmem przy podstawie 2 i zapisujemy log₂ n. Inaczej: to wykładnik, do którego trzeba podnieść 2, żeby dostać n. Na przykład log₂ 1024 = 10, bo 2¹⁰ = 1024.
Nie musisz umieć liczyć logarytmów dokładnie. Wystarczy jedna obserwacja: 2¹⁰ ≈ 1000. Każde „razy tysiąc” to tylko 10 obrotów więcej. Dlatego logarytm z liczb, które spotkasz w zadaniach, nigdy nie przekracza około 60.
Podwajanie — to samo od drugiej strony
long long n;
cin >> n;
int ile = 0;
for (long long p = 1; p <= n; p *= 2) {
cout << p << " ";
ile++;
}
cout << "\n" << ile << "\n";
Pętla, której licznik podwaja się, robi tyle obrotów, ile potęg dwójki mieści się do n — około log₂ n + 1. Dla n = 100 to 7 obrotów (od 1 do 64), dla miliarda — 30.
Uwaga na typ licznika: przy n bliskim 10¹⁸ licznik p dochodzi do około 10¹⁸, a p * 2 — do 2 · 10¹⁸. W int przepełniłby się już przy 2 miliardach i pętla nie skończyłaby się nigdy.
Zgadnij liczbę w 20 pytaniach
Pomyśl liczbę od 1 do miliona. Ile pytań typu „czy Twoja liczba jest większa niż …?” potrzebuję, żeby ją odgadnąć? Najlepsza strategia to pytać zawsze o środek przedziału, w którym liczba może jeszcze być. Każda odpowiedź wyrzuca połowę możliwości — więc po około log₂ 1 000 000 ≈ 20 pytaniach zostaje jedna liczba. Wypróbuj w ramce: wybierz zakres, a potem klikaj „Pytanie”.
long long n, x; // zakres 1..n, sekret x
cin >> n >> x;
long long l = 1, r = n;
int pytania = 0;
while (l < r) {
long long s = (l + r) / 2;
pytania++; // pytanie: czy x > s?
if (x > s) l = s + 1;
else r = s;
}
cout << l << " po " << pytania << " pytaniach\n";
Program pilnuje przedziału [l, r], w którym na pewno jest sekret. Pyta o środek s: jeśli sekret jest większy, wyrzuca lewą połowę (l = s + 1), w przeciwnym razie — prawą (r = s). Gdy l i r się spotkają, liczba jest znaleziona.
Dla miliona wystarczyło 20 pytań, dla tryliona — 60. Gdyby zgadywać po kolei (1? 2? 3?…), trzeba by do miliona pytań. To wyszukiwanie binarne — wrócimy do niego w części 8, gdzie będziemy tak szukać w posortowanych danych.
Szybkie potęgowanie — przypomnienie
long long a, b, m;
cin >> a >> b >> m;
long long w = 1, kroki = 0;
a %= m;
while (b > 0) {
if (b % 2 == 1) w = w * a % m;
a = a * a % m;
b /= 2; // wykładnik maleje o połowę
kroki++;
}
cout << w << " (" << kroki << " krokow)\n";
W lekcji o modulo liczyłeś aᵇ mod m sposobem, który w każdym kroku dzieli wykładnik na pół: zamiast mnożyć a przez siebie b razy, podnosi je do kwadratu (a², a⁴, a⁸, …) i bierze tylko potrzebne kawałki.
Teraz widać, dlaczego jest szybki: pętla działa, dopóki b > 0, a b w każdym obrocie maleje o połowę — czyli robi około log₂ b obrotów. Dla b = 10¹⁸ to 60 kroków zamiast 10¹⁸ mnożeń. Różnica między „natychmiast” a „nigdy”.
log₂ n obrotów: 10 dla tysiąca, 20 dla miliona, 30 dla miliarda, 60 dla 10¹⁸. Dzielenie przez 10 (cyfry liczby) daje jeszcze mniej obrotów — tyle, ile cyfr. Zgadywanie środka przedziału i szybkie potęgowanie to dwa najważniejsze przykłady.
Najpierw policz obroty w głowie — pomaga pamiętać, że 2¹⁰ to około tysiąc — a dopiero potem kliknij „Pokaż odpowiedź”.
int n = 64, ile = 0;
while (n > 1) { n /= 2; ile++; }
cout << ile;
Pokaż odpowiedź
int n = 100, ile = 0;
while (n > 1) { n /= 2; ile++; }
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int p = 1; p <= 1000; p *= 2) ile++;
cout << ile;
Pokaż odpowiedź
long long n = 1000000000, ile = 0;
while (n > 0) { n /= 10; ile++; }
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int p = 1; p <= 1000; p *= 3) ile++;
cout << ile;
Pokaż odpowiedź
long long l = 1, r = 1000000, x = 1, pyt = 0;
while (l < r) {
long long s = (l + r) / 2;
pyt++;
if (x > s) l = s + 1; else r = s;
}
cout << pyt;
Pokaż odpowiedź
int ile = 0;
for (int i = 1; i <= 8; i++)
for (int p = 1; p <= 8; p *= 2) ile++;
cout << ile;
Pokaż odpowiedź
long long b = 1000000, kroki = 0;
while (b > 0) { b /= 2; kroki++; }
cout << kroki;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Notacja O — jak rośnie praca, gdy rosną dane
Dokładne liczenie obrotów bywa żmudne. Program z trzema pętlami może wykonać na przykład 3n² + 5n + 7 obrotów. Ale gdy n jest duże, większość tego wzoru przestaje mieć znaczenie. Dla n = 10⁶: 3n² to 3 · 10¹², 5n to tylko 5 · 10⁶, a 7 to… 7. Liczy się wyłącznie najszybciej rosnący składnik.
Programiści mówią więc krótko: ten program ma złożoność O(n²) (czytaj: „o od n kwadrat”). Notacja O opisuje kształt wzrostu pracy — co się stanie, gdy danych będzie dwa, dziesięć, tysiąc razy więcej. Nie mówi, ile sekund dokładnie potrwa program, ale mówi, czy ma szansę zdążyć.
Dwie zasady upraszczania
| dokładnie obrotów | złożoność | dlaczego |
|---|---|---|
| 3n + 100 | O(n) | stała 3 i +100 odpadają |
| 26 · n | O(n) | stała 26 odpada |
| n · (n − 1) / 2 | O(n²) | to n²/2 − n/2 |
| n² + n | O(n²) | n rośnie wolniej niż n² |
| n · log₂ n + n | O(n log n) | n rośnie wolniej |
| log₂ n + 5 | O(log n) | +5 odpada |
| 1000 | O(1) | stała — nie zależy od n |
| 2ⁿ + n³ | O(2ⁿ) | 2ⁿ rośnie najszybciej |
Zasada 1: zostaw tylko najszybciej rosnący składnik. W n² + n przy dużym n składnik n jest jak kropla w morzu.
Zasada 2: pomiń stałe mnożniki. 3n i n to obie „praca proporcjonalna do n”. Stała zależy od szczegółów — od tego, ile działań jest w jednym obrocie, jak szybki jest komputer — a my chcemy opisać sam pomysł.
O(1) czytamy „stała złożoność”: program wykonuje tyle samo pracy dla n = 10 i dla n = 10¹⁸. Tak działa każdy wzór — na przykład n · (n + 1) / 2 zamiast pętli.
Klasy złożoności — od najszybszej
| złożoność | nazwa | typowy kod | n = 10⁶ |
|---|---|---|---|
| O(1) | stała | wzór, v[i], v.size() | 1 |
| O(log n) | logarytmiczna | połowienie, lower_bound | 20 |
| O(√n) | pierwiastkowa | pętla d * d <= n | 1000 |
| O(n) | liniowa | jedna pętla po danych | 10⁶ |
| O(n log n) | „n log n” | sort | 2 · 10⁷ |
| O(n²) | kwadratowa | pętla w pętli | 10¹² |
| O(n³) | sześcienna | trzy pętle | 10¹⁸ |
| O(2ⁿ) | wykładnicza | wszystkie podzbiory (maski) | liczba o 300 000 cyfrach |
| O(n!) | silnia | wszystkie permutacje | jeszcze więcej |
Na wykresie poniżej widać, jak różnie rosną te funkcje już dla małych n. 2ⁿ wylatuje poza wykres przy n ≈ 9, n² — przy n = 20, a log n prawie się nie podnosi.
Co się stanie, gdy danych będzie 10 razy więcej?
| złożoność | dane × 10 | czas |
|---|---|---|
| O(1) | × 10 | bez zmian |
| O(log n) | × 10 | + ok. 3 kroki |
| O(n) | × 10 | × 10 |
| O(n log n) | × 10 | × ok. 11–12 |
| O(n²) | × 10 | × 100 |
| O(n³) | × 10 | × 1000 |
| O(2ⁿ) | n + 10 | × 1024 |
To najbardziej praktyczny sposób myślenia o złożoności. Program O(n²), który dla 1000 liczb działa 0,01 s, dla 10 000 liczb będzie działał 1 s, a dla 100 000 — 100 s. Program O(n) w tej samej sytuacji: 0,01 s, 0,1 s, 1 s.
Przy O(2ⁿ) wystarczy dodać 10 elementów, żeby praca wzrosła ponad tysiąc razy. Dlatego „sprawdzanie wszystkich możliwości” działa tylko dla bardzo małych danych — n do około 20.
long long a = 0, b = 0;
for (int i = 0; i < 1000; i++)
for (int j = 0; j < 1000; j++) a++;
for (int i = 0; i < 10000; i++)
for (int j = 0; j < 10000; j++) b++;
cout << a << " " << b << " " << b / a << "\n";
Czasomierz: ile to potrwa?
Ramka liczy, ile operacji wykonuje każda klasa złożoności dla wybranego n i ile to zajmie przy 100 milionach operacji na sekundę. Zielone zdąży w sekundę, żółte — w minutę, czerwone nie zdąży nigdy w rozsądnym czasie. Przesuń suwak do miliona i popatrz na O(n²).
Stałe mają znaczenie — ale tylko dla małych n
| n | program A: 1000 · n | program B: n² | szybszy |
|---|---|---|---|
| 10 | 10 000 | 100 | B |
| 100 | 100 000 | 10 000 | B |
| 1000 | 10⁶ | 10⁶ | remis |
| 10⁴ | 10⁷ | 10⁸ | A |
| 10⁶ | 10⁹ | 10¹² | A — tysiąc razy |
Program A jest liniowy, ale „ciężki” — w każdym obrocie robi 1000 działań. Program B jest kwadratowy, ale lekki. Dla małych n wygrywa B! Dopiero od n = 1000 lepszy jest A — i od tego miejsca jego przewaga tylko rośnie.
Dlatego notacja O pomija stałe: w zadaniach olimpijskich dane są duże, a przy dużych danych zawsze wygrywa lepszy kształt. Stałą poprawisz drobnymi sztuczkami, a złej złożoności — tylko nowym pomysłem.
Ukryte koszty — pętle, których nie widać
Nie każda pętla jest napisana wprost. Wiele poleceń z biblioteki C++ to pętle ukryte w środku. Wywołane raz — nie szkodzą. Wywołane w pętli — mnożą pracę.
| polecenie | koszt | uwaga |
|---|---|---|
v[i], v.size(), v.push_back(x), v.back() | O(1) | szybkie |
s += c, s.push_back(c) | O(1) | dopisanie na koniec |
sort(v.begin(), v.end()) | O(n log n) | raz — świetnie, w pętli — źle |
count, find, max_element, reverse | O(n) | przechodzą cały zakres |
v.erase(v.begin()), v.insert(v.begin(), x) | O(n) | przesuwają wszystkie elementy |
s = s + c, s.substr(…), kopia vectora | O(n) | tworzą nową kopię całości |
lower_bound, binary_search (na posortowanym) | O(log n) | połowienie |
string s;
for (int i = 0; i < 1000000; i++) {
s = s + 'a'; // kopiuje cały napis!
}
cout << s.size() << "\n";
string s;
for (int i = 0; i < 1000000; i++) {
s += 'a'; // dopisuje na koniec
}
cout << s.size() << "\n";
Oba programy budują napis z miliona liter. Lewy w każdym obrocie tworzy nowy napis: kopiuje wszystkie dotychczasowe litery i dokleja jedną — w obrocie numer i to i działań. Razem 1 + 2 + … + n ≈ n²/2, czyli O(n²): pół biliona kopiowań. Prawy tylko dopisuje literę na koniec — O(1) na obrót, O(n) razem. Ta sama różnica dotyczy v.erase(v.begin()) w pętli: usuwanie z początku vectora przesuwa wszystkie pozostałe elementy.
3n² + 5n + 7 to O(n²). Kolejność od najszybszej: O(1), O(log n), O(√n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!). Dane × 10 → O(n) × 10, O(n²) × 100. Liczy się też to, czego nie widać: sort, count, erase, s = s + c wywołane w pętli mnożą pracę.
Najpierw odpowiedz w głowie — pomyśl, jak rośnie praca — a dopiero potem kliknij „Pokaż odpowiedź”.
long long a = 0, b = 0;
for (int i = 0; i < 300; i++) a++;
for (int i = 0; i < 3000; i++) b++;
cout << b / a;
Pokaż odpowiedź
long long a = 0, b = 0;
for (int i = 0; i < 300; i++)
for (int j = 0; j < 300; j++) a++;
for (int i = 0; i < 900; i++)
for (int j = 0; j < 900; j++) b++;
cout << b / a;
Pokaż odpowiedź
int a = 0, b = 0;
for (int n = 1000; n > 1; n /= 2) a++;
for (int n = 1000000; n > 1; n /= 2) b++;
cout << b - a;
Pokaż odpowiedź
int n = 100, ile = 0;
for (int i = 0; i < n; i++) ile++;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) ile++;
cout << ile;
Pokaż odpowiedź
int n = 10, ile = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 26; j++) ile++;
cout << ile;
Pokaż odpowiedź
long long n1 = 100, n2 = 10000;
cout << (1000 * n1 > n1 * n1) << (1000 * n2 > n2 * n2);
Pokaż odpowiedź
string s;
for (int i = 0; i < 5; i++) s = s + "ab";
cout << s.size();
Pokaż odpowiedź
vector<int> v = {1, 2, 3, 4, 5, 6};
long long przesuniecia = 0;
while (!v.empty()) {
przesuniecia += v.size() - 1; // tyle elementów przesuwa erase
v.erase(v.begin());
}
cout << przesuniecia;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Czy zdąży? Ograniczenia z treści i limit czasu
Teraz połączymy liczenie obrotów z zegarkiem. Reguła kciuka zawodników brzmi: komputer wykonuje około 10⁸ (100 milionów) prostych operacji na sekundę. „Prosta operacja” to jeden obrót pętli z kilkoma dodawaniami i porównaniami. Obroty z dzieleniem albo modulo na long long są wolniejsze, a bardzo proste — szybsze, ale jako miara „czy zdąży” reguła sprawdza się świetnie.
Najważniejsze jest to, skąd brać n. Każde zadanie ma w treści ograniczenia — na przykład „1 ≤ n ≤ 200 000”. Złożoność liczymy dla największych danych, jakie zadanie dopuszcza, bo właśnie takie będą w ostatnich testach.
Tabela, którą warto znać na pamięć
| ograniczenie | wystarczy złożoność | operacji |
|---|---|---|
| n ≤ 10 | O(n!) | 3,6 · 10⁶ |
| n ≤ 20 | O(2ⁿ) | 10⁶ |
| n ≤ 500 | O(n³) | 1,25 · 10⁸ |
| n ≤ 5000 | O(n²) | 2,5 · 10⁷ |
| n ≤ 10⁶ | O(n log n) | 2 · 10⁷ |
| n ≤ 10⁸ | O(n) | 10⁸ |
| n ≤ 10¹² | O(√n) | 10⁶ |
| n ≤ 10¹⁸ | O(log n) albo O(1) | 60 |
Czytaj tabelę w dwie strony. Gdy masz pomysł — sprawdź, czy jego złożoność mieści się w ograniczeniu. Gdy nie masz pomysłu — ograniczenie podpowiada, jakiego rozwiązania szuka autor zadania.
Przykłady: „n ≤ 200 000” — pętla w pętli to 4 · 10¹⁰ operacji, czyli kilka minut; za to sortowanie to około 3,5 · 10⁶ — natychmiast. „n ≤ 18” — autor zadania wręcz zaprasza do sprawdzenia wszystkich podzbiorów. „n ≤ 10¹⁸” — żadna pętla po n nie wchodzi w grę, potrzebny jest wzór albo połowienie.
long long n;
cin >> n;
long long kwadrat = n * n;
cout << "n^2 = " << kwadrat;
if (kwadrat <= 100000000) cout << " - zdazy\n";
else cout << " - za wolno\n";
Limit czasu w sprawdzarce
Nasza sprawdzarka uruchamia Twój program na każdym teście i mierzy czas. Jeśli program liczy dłużej niż limit (w tej lekcji 1 sekunda), dostaje Time limit exceeded — w skrócie TLE. Dalszych testów sprawdzarka już nie uruchamia, bo są zwykle jeszcze większe. Program, który „wisi” w nieskończonej pętli, zostaje przerwany po kilkunastu sekundach — też z TLE.
Testy są ułożone od najmniejszych do największych. Dlatego wolne rozwiązanie często zalicza kilka pierwszych testów, a dopiero potem dostaje TLE. To dobra wiadomość: pomysł jest poprawny, trzeba go tylko przyspieszyć.
Dane z generatora — wielkie testy w kilku liczbach
Test z milionem liczb zajmuje kilka megabajtów — za dużo, żeby wygodnie wysyłać go przez przeglądarkę. Dlatego w części zadań z tej lekcji liczb nie dostajesz wprost, tylko przepis, jak je wygenerować. Takie dane spotkasz też czasem na olimpiadzie.
Przepis jest zawsze ten sam. W wejściu jest pięć liczb: n, s, a, b, m. Pierwsza liczba ciągu to x₁ = s, a każda następna powstaje z poprzedniej: xᵢ = (xᵢ₋₁ · a + b) mod m. Wszystkie liczby są mniejsze od m.
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, s, a, b, m;
cin >> n >> s >> a >> b >> m;
vector<long long> x(n);
x[0] = s;
for (int i = 1; i < n; i++) {
x[i] = (x[i - 1] * a + b) % m;
}
// dalej: zwykły program na vectorze x
long long suma = 0, maks = x[0];
for (int i = 0; i < n; i++) {
suma += x[i];
maks = max(maks, x[i]);
}
cout << suma << " " << maks << "\n";
return 0;
}
Dla pierwszego wejścia: x₁ = 3, x₂ = (3 · 7 + 1) mod 10 = 2, x₃ = (2 · 7 + 1) mod 10 = 5, x₄ = (5 · 7 + 1) mod 10 = 6, x₅ = (6 · 7 + 1) mod 10 = 3. Suma 3 + 2 + 5 + 6 + 3 = 19, a największa liczba to 6 — dokładnie to wypisuje program. Zanim zaczniesz rozwiązywać zadanie z generatorem, zawsze sprawdź w ten sposób na kartce przykład z treści.
Ważne szczegóły: wszystko w long long — iloczyn xᵢ₋₁ · a może sięgać 10¹⁸. Pierwsza liczba to po prostu s; wzór stosujemy od drugiej. Po wygenerowaniu masz zwykły vector i dalej piszesz program jak zawsze.
Drugie wejście to milion liczb — a program kończy się w kilka setnych sekundy, bo cała praca to dwie pętle po n.
Ten sam problem, dwa pomysły
Ile jest różnych liczb w ciągu? Pierwszy pomysł: dla każdej liczby sprawdź, czy wystąpiła już wcześniej — pętla w pętli, O(n²). Drugi pomysł, z lekcji o tablicach: liczby są mniejsze od m, więc zaznaczaj je w tablicy bool — jedno przejście, O(n + m).
// x — ciąg z generatora, n = 1 000 000
int rozne = 0;
for (int i = 0; i < n; i++) {
bool bylo = false;
for (int j = 0; j < i; j++)
if (x[j] == x[i]) bylo = true;
if (!bylo) rozne++;
}
cout << rozne << "\n"; // pół biliona porównań
// x — ciąg z generatora, wszystkie x[i] < m <= 10^6
vector<bool> bylo(m, false);
int rozne = 0;
for (int i = 0; i < n; i++) {
if (!bylo[x[i]]) {
bylo[x[i]] = true;
rozne++;
}
}
cout << rozne << "\n"; // milion kroków
Najpierw oszacuj w głowie — liczba operacji i reguła 10⁸ na sekundę — a dopiero potem kliknij „Pokaż odpowiedź”.
long long n = 30000;
cout << n * n;
Pokaż odpowiedź
long long n = 30000;
cout << n * 15;
Pokaż odpowiedź
long long n = 400;
cout << (n * n * n <= 100000000);
Pokaż odpowiedź
long long n = 1000;
cout << (n * n * n <= 100000000);
Pokaż odpowiedź
cout << (1 << 20);
Pokaż odpowiedź
long long x = 1;
cout << x;
for (int i = 2; i <= 4; i++) {
x = (x * 2 + 3) % 10;
cout << " " << x;
}
Pokaż odpowiedź
long long x = 3, suma = 3;
for (int i = 2; i <= 5; i++) {
x = (x * 7 + 1) % 10;
suma += x;
}
cout << suma;
Pokaż odpowiedź
long long n = 1000000000000, ile = 0;
for (long long d = 1; d * d <= n; d++) ile++;
cout << ile;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Wzór zamiast pętli, pierwiastek zamiast n
Wiesz już, jak policzyć, czy program zdąży. Teraz zaczniemy go przyspieszać. Pierwsze dwa sposoby są czysto matematyczne. Wzór zamienia pętlę O(n) w jedno działanie — O(1). Pierwiastek zamienia pętlę po wszystkich liczbach do n w pętlę do √n — dla n = 10¹² to milion kroków zamiast biliona.
Suma od a do b
long long a, b;
cin >> a >> b;
long long ile = b - a + 1; // ile liczb
long long suma = (a + b) * ile / 2; // średnia razy ile
cout << suma << "\n";
Sztuczka Gaussa działa dla każdego ciągu kolejnych liczb: pierwsza plus ostatnia daje tyle samo co druga plus przedostatnia. Każda para to a + b, a par jest „ile / 2”. Stąd suma = (a + b) · ile / 2, gdzie ile = b − a + 1.
Sprawdź: 3 + 4 + 5 + 6 + 7 = 25 = (3 + 7) · 5 / 2. Dla przedziału od −10⁹ do 10⁹ liczby ujemne i dodatnie się znoszą — wychodzi 0.
Dzielenie przez 2 robimy na końcu: iloczyn (a + b) · ile jest zawsze parzysty, więc dzielenie jest dokładne. Gdybyś dzielił wcześniej, przy nieparzystym ile zgubiłbyś połówkę.
Ile wielokrotności i ich suma
long long n, k;
cin >> n >> k;
long long ile = n / k; // k, 2k, ..., ile*k
long long suma = k * (ile * (ile + 1) / 2);
cout << ile << " " << suma << "\n";
Wielokrotności k nie większe od n to k, 2k, 3k, …, ile · k, gdzie ile = n / k (dzielenie całkowite). Dla n = 20 i k = 3: 3, 6, 9, 12, 15, 18 — sześć liczb.
Ich suma to k · (1 + 2 + … + ile) — wyciągamy k przed nawias, a w środku zostaje znana suma 1 + … + ile = ile · (ile + 1) / 2. Dla przykładu: 3 · 21 = 63.
A ile wielokrotności k leży w przedziale od a do b? Tyle, ile do b, minus tyle, ile do a − 1: b / k - (a - 1) / k (dla a ≥ 1).
Podzielne przez 3 lub przez 5 — włączanie i wyłączanie
long long n;
cin >> n;
long long wynik = n / 3 + n / 5 - n / 15;
cout << wynik << "\n";
Ile liczb od 1 do n dzieli się przez 3 lub przez 5? Podzielnych przez 3 jest n / 3, przez 5 — n / 5. Ale liczby podzielne przez obie (15, 30, …) policzyliśmy dwa razy! Trzeba je raz odjąć: n / 15.
Dla n = 20: przez 3 — 6 liczb, przez 5 — 4 liczby, przez 15 — jedna (15). Razem 6 + 4 − 1 = 9: to 3, 5, 6, 9, 10, 12, 15, 18, 20.
To zasada włączania i wyłączania: dodaj grupy, odejmij to, co się nakłada. Pętla po n = 10¹⁸ byłaby niemożliwa — wzór odpowiada natychmiast.
Od O(n²) przez O(n) do O(1): pary o sumie s
long long n, s; // pary 1 <= a < b <= n, a + b = s
cin >> n >> s;
long long od = max(1LL, s - n); // najmniejsze a
long long doo = (s - 1) / 2; // największe a (a < b)
long long ile = 0;
if (od <= doo) ile = doo - od + 1;
cout << ile << "\n";
W lekcji o pętli for liczyłeś pary a < b z przedziału od 1 do n o sumie s. Najpierw dwiema pętlami — O(n²). Potem zauważyłeś, że b = s − a, i wystarczyła jedna pętla po a — O(n).
Można jeszcze lepiej: a nie może być mniejsze od 1 ani od s − n (bo wtedy b > n), i musi być mniejsze od b, czyli a ≤ (s − 1) / 2. Dobre a tworzą przedział, a liczbę liczb w przedziale znasz z części 1: koniec − początek + 1. Jedno działanie — O(1), nawet dla n = 10¹².
Pierwiastek: dzielniki chodzą parami
long long n;
cin >> n;
long long ile = 0;
for (long long d = 1; d * d <= n; d++) {
if (n % d == 0) {
ile++; // d
if (d != n / d) ile++; // i jego para n / d
}
}
cout << ile << "\n";
Przypomnienie z lekcji o pętli for: jeśli d dzieli n, to n / d też dzieli n, a w każdej parze mniejszy dzielnik jest co najwyżej √n. Wystarczy więc pętla d * d <= n — O(√n) zamiast O(n).
Drugie wejście to liczba bliska biliona z bardzo wieloma dzielnikami (6720!). Pętla do n wykonałaby bilion obrotów — kilka godzin. Pętla do pierwiastka — niecały milion, ułamek sekundy.
Pamiętaj o long long dla d: przy n do 10¹² iloczyn d · d dochodzi do 10¹².
Rozkład na czynniki pierwsze w O(√n)
long long n;
cin >> n;
for (long long p = 2; p * p <= n; p++) {
while (n % p == 0) {
cout << p << " ";
n /= p;
}
}
if (n > 1) cout << n; // została jedna duża liczba pierwsza
cout << "\n";
Dzielimy n przez kolejne liczby p, dopóki się da. Warunek pętli p * p <= n sprawdza się dla aktualnego n, które maleje po każdym dzieleniu — pętla kończy się jeszcze szybciej.
Dlaczego po pętli wystarczy sprawdzić n > 1? Jeśli zostało coś większego od 1, to nie ma dzielników nie większych od swojego pierwiastka — więc jest liczbą pierwszą. Drugie wejście to liczba pierwsza: pętla przejdzie do miliona i wypisze samą liczbę.
Ile kwadratów do n? Pierwiastek z poprawką
long long n;
cin >> n;
long long k = sqrtl(n); // przybliżenie
while (k * k > n) k--; // poprawka w dół
while ((k + 1) * (k + 1) <= n) k++; // poprawka w górę
cout << k << "\n";
Kwadratów liczb całkowitych od 1 do n (1, 4, 9, …) jest tyle, ile wynosi część całkowita z √n: dla n = 50 to 1, 4, 9, 16, 25, 36, 49 — siedem. Pętla k * k <= n byłaby O(√n) — dla n = 10¹⁸ to miliard kroków, już za dużo.
Funkcja sqrtl (pierwiastek na liczbach o większej dokładności) liczy to od razu, ale — jak pamiętasz z lekcji o zaokrąglaniu — przy wielkich liczbach może pomylić się o 1. Dlatego dwie krótkie pętle poprawiają wynik. Każda wykona najwyżej kilka obrotów, więc całość to O(1).
(a + b) · (b − a + 1) / 2. Wielokrotności k do n: n / k, ich suma k · m · (m + 1) / 2 dla m = n / k. „Przez 3 lub przez 5”: n/3 + n/5 − n/15. Dzielniki, pierwszość i rozkład — pętla d * d <= n, O(√n). Pierwiastek całkowity: sqrtl plus poprawka.
Najpierw policz w głowie — wzorem, nie pętlą — a dopiero potem kliknij „Pokaż odpowiedź”.
long long a = 10, b = 20;
cout << (a + b) * (b - a + 1) / 2;
Pokaż odpowiedź
cout << 100 / 7;
Pokaż odpowiedź
long long a = 50, b = 100, k = 7;
cout << b / k - (a - 1) / k;
Pokaż odpowiedź
long long n = 30;
cout << n / 2 + n / 3 - n / 6;
Pokaż odpowiedź
long long n = 10000, ile = 0;
for (long long d = 1; d * d <= n; d++) ile++;
cout << ile;
Pokaż odpowiedź
long long n = 100, ile = 0;
for (long long d = 1; d * d <= n; d++)
if (n % d == 0) ile += (d * d == n ? 1 : 2);
cout << ile;
Pokaż odpowiedź
long long n = 84;
for (long long p = 2; p * p <= n; p++)
while (n % p == 0) { cout << p << " "; n /= p; }
if (n > 1) cout << n;
Pokaż odpowiedź
long long n = 10, s = 15;
long long od = max(1LL, s - n), doo = (s - 1) / 2;
cout << (od <= doo ? doo - od + 1 : 0);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Policz raz, korzystaj wiele razy
Bardzo częsta przyczyna wolnych programów: ta sama praca wykonywana w kółko. Zadanie zadaje q pytań o te same dane, a program dla każdego pytania przechodzi wszystkie dane od nowa — O(n · q). Rozwiązanie: raz przygotować pomocniczą tablicę (O(n)), a potem odpowiadać na każde pytanie natychmiast (O(1)). Razem O(n + q).
Sumy prefiksowe — suma przedziału jednym odejmowaniem
Pytanie: ile wynosi suma liczb od pozycji l do pozycji r? Pętla od l do r to do n obrotów na pytanie. Przy n = 10⁶ i q = 10⁵ pytań to 10¹¹ — za wolno.
Pomysł z lekcji o vectorze: policz sumy prefiksowe P[i] = t[1] + t[2] + … + t[i], z P[0] = 0. Wtedy suma od l do r to wszystko do r minus wszystko przed l:
Tablicę P liczy jedna pętla: P[i] = P[i - 1] + t[i].
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> P(n + 1, 0); // P[0] = 0
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
P[i] = P[i - 1] + x;
}
for (int k = 0; k < q; k++) {
int l, r;
cin >> l >> r;
cout << P[r] - P[l - 1] << "\n"; // O(1) na pytanie
}
return 0;
}
Numerujemy od 1, żeby P[l − 1] miało sens także dla l = 1 (wtedy odejmujemy P[0] = 0). Pętla wczytująca od razu liczy sumy — dane nie są nawet potrzebne w osobnej tablicy.
Dla pytania (3, 6): P[6] = 23, P[2] = 4, więc suma = 19 — to 4 + 1 + 5 + 9. Pytanie o cały ciąg (1, 8) to P[8] − P[0] = 31.
Złożoność: O(n) na przygotowanie i O(1) na każde z q pytań — O(n + q). Ten sam pomysł działa dla „ile jest liczb parzystych na przedziale” — sumujemy wtedy jedynki tam, gdzie liczba jest parzysta.
Tablica zliczeń — „ile razy?” w O(1)
// x — ciąg z generatora, wartości mniejsze od m
vector<int> ile(m, 0);
for (int i = 0; i < n; i++) ile[x[i]]++; // raz: O(n)
int q;
cin >> q;
for (int k = 0; k < q; k++) {
int y;
cin >> y;
cout << ile[y] << "\n"; // pytanie: O(1)
}
Znasz to z lekcji o tablicach: gdy wartości są małe (mniejsze od m), możesz zrobić tablicę liczników indeksowaną samą wartością. Jedno przejście zlicza wszystko, a potem odpowiedź na „ile razy wystąpiło y?” to odczyt ile[y].
Bez tablicy zliczeń każde pytanie to przejście całego ciągu (albo count — ukryta pętla!) — O(n · q). Z tablicą: O(n + m + q). Warunek: m musi być na tyle małe, żeby tablica zmieściła się w pamięci — do kilkudziesięciu milionów.
Sito Eratostenesa — wszystkie liczby pierwsze naraz
int n;
cin >> n;
vector<bool> zlozona(n + 1, false);
int pierwszych = 0;
for (long long i = 2; i <= n; i++) {
if (zlozona[i]) continue;
pierwszych++; // i jest pierwsza
for (long long j = i * i; j <= n; j += i) zlozona[j] = true;
}
cout << pierwszych << "\n";
Ile jest liczb pierwszych do 10 milionów? Sprawdzanie każdej liczby pętlą do pierwiastka to około n · √n / 2 ≈ 10¹⁰ działań — za wolno. Sito z lekcji o tablicach robi to „hurtem”: każda liczba pierwsza i wykreśla swoje wielokrotności.
Ile to kosztuje? Liczba 2 wykreśla n / 2 liczb, 3 — n / 3, 5 — n / 5… Razem n · (1/2 + 1/3 + 1/5 + …) — ta suma rośnie tak wolno, że sito działa praktycznie jak O(n). Dla 10⁷ to kilkadziesiąt milionów prostych kroków — mniej niż sekunda.
Tablica różnic — dodaj do całego przedziału w O(1)
int n, q;
cin >> n >> q;
vector<long long> d(n + 2, 0);
for (int k = 0; k < q; k++) {
int l, r;
long long v;
cin >> l >> r >> v;
d[l] += v; // od l w górę: +v
d[r + 1] -= v; // od r + 1: z powrotem
}
long long t = 0;
for (int i = 1; i <= n; i++) {
t += d[i]; // suma prefiksowa różnic
cout << t << " ";
}
cout << "\n";
Odwrotny problem: q poleceń „dodaj v do wszystkich pozycji od l do r”, a na końcu wypisz całą tablicę. Pętla od l do r w każdym poleceniu to O(n · q).
Sztuczka: zamiast dodawać v do każdej pozycji, zapisz tylko zmiany: „od pozycji l wartość rośnie o v” (d[l] += v) i „od pozycji r + 1 wraca” (d[r + 1] -= v). Na końcu suma prefiksowa tablicy d odtwarza wszystkie wartości. Każde polecenie to O(1), całość O(n + q).
Sprawdź: pozycja 4 dostaje 1 (z polecenia 2) i 10 (z polecenia 3) — razem 11.
Okno o stałej długości — przesuwaj, nie licz od nowa
int n = 8, k = 3;
int t[8] = {3, 1, 4, 1, 5, 9, 2, 6};
long long okno = 0;
for (int i = 0; i < k; i++) okno += t[i]; // pierwsze okno
long long naj = okno;
for (int i = k; i < n; i++) {
okno += t[i] - t[i - k]; // wchodzi t[i], wychodzi t[i-k]
naj = max(naj, okno);
}
cout << naj << "\n";
Największa suma k kolejnych liczb. Liczenie każdego okna od nowa to O(n · k). Ale sąsiednie okna różnią się tylko dwiema liczbami: przy przesunięciu o jedno miejsce jedna liczba wchodzi z prawej, a jedna wychodzi z lewej.
Wystarczy więc poprawić sumę o dwie liczby — O(1) na przesunięcie, O(n) razem. Najlepsze okno to 1 + 5 + 9 = 15? Nie — 5 + 9 + 2 = 16? Też nie: 9 + 2 + 6 = 17. Program sprawdza wszystkie okna za nas.
P[i] = P[i-1] + t[i], odpowiedź P[r] - P[l-1]. „Ile razy?” przy małych wartościach: tablica zliczeń. Wszystkie liczby pierwsze do n: sito. Dodawanie do przedziałów: tablica różnic d[l] += v, d[r+1] -= v i suma prefiksowa na końcu. Okna stałej długości: dodaj wchodzącą, odejmij wychodzącą.
Najpierw policz w głowie — wypisz sobie tablicę P albo d na kartce — a dopiero potem kliknij „Pokaż odpowiedź”.
int t[6] = {0, 2, 7, 1, 8, 2}; // t[1..5]
int P[6] = {0};
for (int i = 1; i <= 5; i++) P[i] = P[i - 1] + t[i];
cout << P[4] - P[1];
Pokaż odpowiedź
int t[6] = {0, 2, 7, 1, 8, 2};
int P[6] = {0};
for (int i = 1; i <= 5; i++) P[i] = P[i - 1] + t[i];
cout << P[5] - P[0];
Pokaż odpowiedź
long long n = 1000000;
cout << n;
Pokaż odpowiedź
int t[7] = {4, 1, 4, 3, 1, 4, 2};
int ile[5] = {0};
for (int i = 0; i < 7; i++) ile[t[i]]++;
cout << ile[4] << " " << ile[2] << " " << ile[0];
Pokaż odpowiedź
int d[7] = {0};
d[2] += 5; d[5] -= 5; // +5 na pozycjach 2..4
d[1] += 1; d[4] -= 1; // +1 na pozycjach 1..3
int t = 0;
for (int i = 1; i <= 5; i++) { t += d[i]; cout << t << " "; }
Pokaż odpowiedź
int t[6] = {2, 7, 1, 8, 2, 8};
int k = 2, okno = t[0] + t[1], naj = okno;
for (int i = k; i < 6; i++) {
okno += t[i] - t[i - k];
naj = max(naj, okno);
}
cout << naj;
Pokaż odpowiedź
int n = 30, ile = 0;
vector<bool> z(n + 1, false);
for (int i = 2; i <= n; i++) {
if (z[i]) continue;
ile++;
for (int j = i * i; j <= n; j += i) z[j] = true;
}
cout << ile;
Pokaż odpowiedź
long long n = 1000, q = 1000;
cout << n * q << " " << n + q;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Sortuj raz, szukaj szybko
Ostatni, bardzo ważny sposób na przyspieszenie: posortuj dane raz (O(n log n)), a potem korzystaj z porządku. W posortowanym ciągu szukanie liczby to zgadywanka z części 3 — O(log n) zamiast O(n). Równe liczby stoją obok siebie, najbliższe też. A dwa wskaźniki potrafią przejść po posortowanych danych w O(n) tam, gdzie zwykłe sprawdzanie par kosztowałoby O(n²).
lower_bound — połowienie w posortowanym ciągu
Z lekcji o sortowaniu znasz lower_bound: w posortowanym ciągu zwraca strzałkę na pierwszy element nie mniejszy niż x. W środku działa dokładnie jak zgadywanie liczby — patrzy na środek przedziału i wyrzuca połowę. Prześledź to w ramce. Zobacz, ile kroków potrzeba dla 16 liczb, a ile potrzebowałoby szukanie po kolei.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end()); // raz: O(n log n)
for (int k = 0; k < q; k++) {
int a, b;
cin >> a >> b; // ile liczb w [a, b]?
auto od = lower_bound(v.begin(), v.end(), a);
auto za = upper_bound(v.begin(), v.end(), b);
cout << za - od << "\n"; // każde pytanie: O(log n)
}
return 0;
}
Ile liczb leży w przedziale [a, b]? Po posortowaniu (1, 3, 9, 9, 12, 15, 20, 27) wszystkie takie liczby stoją obok siebie. lower_bound(a) wskazuje pierwszą z nich, a upper_bound(b) — pierwszą większą od b. Różnica strzałek to liczba elementów między nimi.
Dla [5, 15]: od 9 do 15 włącznie — 9, 9, 12, 15, czyli 4. Dla [10, 10] — żadnej.
Złożoność: sortowanie raz O(n log n), każde pytanie O(log n) — razem O((n + q) log n). Bez sortowania każde pytanie to przejście całego ciągu: O(n · q).
Dwa wskaźniki — para o sumie k w O(n)
vector<int> v = {8, 1, 11, 4, 6, 15, 3};
int k = 14;
sort(v.begin(), v.end()); // 1 3 4 6 8 11 15
int l = 0, r = v.size() - 1;
bool jest = false;
while (l < r) {
int s = v[l] + v[r];
if (s == k) { jest = true; break; }
if (s < k) l++; // za mało — większa lewa
else r--; // za dużo — mniejsza prawa
}
if (jest) cout << v[l] << " + " << v[r] << "\n";
else cout << "BRAK\n";
Czy jakieś dwie liczby sumują się do k? Sprawdzanie wszystkich par to O(n²). Po sortowaniu wystarczą dwa wskaźniki: l na najmniejszej liczbie, r na największej.
Jeśli suma jest za mała — przesuwamy l w prawo (większa lewa liczba). Za duża — r w lewo. W każdym kroku jeden wskaźnik się rusza, a spotkają się po najwyżej n krokach: O(n) po sortowaniu, O(n log n) razem.
Dlaczego nic nie gubimy? Gdy v[l] + v[r] < k, liczba v[l] z żadną pozostałą nie da k — bo v[r] jest największa. Można ją bezpiecznie wyrzucić. Tak samo z v[r], gdy suma jest za duża.
Dwa wskaźniki jako okno: najdłuższy fragment o sumie ≤ S
int t[8] = {4, 1, 1, 2, 1, 5, 2, 1}; // liczby nieujemne
int S = 6, n = 8;
int l = 0, naj = 0;
long long suma = 0;
for (int r = 0; r < n; r++) {
suma += t[r]; // poszerz w prawo
while (suma > S) { // za dużo — zwęź z lewej
suma -= t[l];
l++;
}
naj = max(naj, r - l + 1);
}
cout << naj << "\n";
Najdłuższy fragment kolejnych liczb o sumie co najwyżej S. Sprawdzanie każdego fragmentu to O(n²). Ale gdy liczby są nieujemne, okno można przesuwać: prawy koniec r idzie zawsze w prawo, a lewy koniec l dogania go tylko wtedy, gdy suma przekroczy S.
Każdy z dwóch wskaźników przejdzie tablicę najwyżej raz — razem najwyżej 2n kroków, choć w kodzie jest pętla w pętli. To ważna lekcja: pętla while w pętli for nie zawsze oznacza O(n²). Liczy się, ile razy łącznie wykona się wnętrze.
Tu najdłuższy jest fragment 1, 1, 2, 1 o sumie 5 — cztery liczby. Dołożenie czwórki z lewej albo piątki z prawej przekroczyłoby S = 6.
Wyszukiwanie binarne po odpowiedzi
long long n;
cin >> n;
long long l = 0, r = 2000000000; // odpowiedź na pewno jest w [l, r]
while (l < r) {
long long s = (l + r + 1) / 2; // środek zaokrąglony w górę
if (s * s <= n) l = s; // s jest dobre — odpowiedź >= s
else r = s - 1; // s za duże
}
cout << l << "\n";
Połowić można nie tylko dane, ale też możliwe odpowiedzi. Szukamy największego x, dla którego x² ≤ n. Warunek „x² ≤ n” jest prawdziwy dla małych x i fałszywy dla dużych — zmienia się tylko raz. Taki warunek pozwala zgadywać odpowiedź jak liczbę w zgadywance.
Odpowiedź leży gdzieś między 0 a 2 · 10⁹. Bierzemy środek s: jeśli s² ≤ n, odpowiedź jest co najmniej s (l = s); jeśli nie — jest mniejsza (r = s − 1). Około 31 kroków i mamy pierwiastek całkowity — bez sqrt i bez obaw o dokładność.
Uwaga: gdy przypisujemy l = s, środek liczymy z zaokrągleniem w górę, (l + r + 1) / 2. Inaczej przy l = r − 1 pętla stałaby w miejscu.
lower_bound, upper_bound, binary_search — O(log n). Para o sumie k, okno o sumie ≤ S: dwa wskaźniki — O(n), bo każdy wskaźnik idzie tylko w jedną stronę. Gdy odpowiedź „przechodzi z tak na nie” tylko raz — zgaduj ją połowieniem: O(log zakresu).
Najpierw odpowiedz w głowie — wypisz sobie posortowany ciąg — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {7, 2, 9, 4, 4, 1};
sort(v.begin(), v.end());
cout << lower_bound(v.begin(), v.end(), 4) - v.begin();
Pokaż odpowiedź
vector<int> v = {7, 2, 9, 4, 4, 1};
sort(v.begin(), v.end());
cout << upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(), 4);
Pokaż odpowiedź
vector<int> v = {10, 3, 8, 1, 5, 8, 2};
sort(v.begin(), v.end());
auto a = lower_bound(v.begin(), v.end(), 3);
auto b = upper_bound(v.begin(), v.end(), 8);
cout << b - a;
Pokaż odpowiedź
int n = 1000000, kroki = 0;
while (n > 1) { n = (n + 1) / 2; kroki++; }
cout << kroki;
Pokaż odpowiedź
vector<int> v = {1, 2, 4, 7, 11};
int k = 9, l = 0, r = 4;
while (l < r && v[l] + v[r] != k) {
if (v[l] + v[r] < k) l++; else r--;
}
cout << v[l] << " " << v[r];
Pokaż odpowiedź
int t[8] = {5, 5, 5, 5, 5, 5, 5, 5};
int l = 0, ile = 0, suma = 0;
for (int r = 0; r < 8; r++) {
suma += t[r];
while (suma > 10) { suma -= t[l]; l++; ile++; }
}
cout << ile;
Pokaż odpowiedź
long long n = 1000, l = 0, r = 100;
while (l < r) {
long long s = (l + r + 1) / 2;
if (s * s * s <= n) l = s; else r = s - 1;
}
cout << l;
Pokaż odpowiedź
long long l = 0, r = 2000000000, kroki = 0;
while (l < r) { long long s = (l + r + 1) / 2; kroki++; if (s <= 7) l = s; else r = s - 1; }
cout << kroki;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: szybkie programy w praktyce
Znasz już wszystkie narzędzia: liczenie obrotów pojedynczych i zagnieżdżonych pętli, logarytm i połowienie, notację O z ukrytymi kosztami, regułę 10⁸ operacji na sekundę i tabelę ograniczeń, dane z generatora, a do tego zestaw sposobów na przyspieszanie: wzory, pętlę do pierwiastka, sumy prefiksowe, tablice zliczeń, sito, tablicę różnic, okna, sortowanie z lower_bound, dwa wskaźniki i wyszukiwanie binarne po odpowiedzi. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka, potem zadania średnie, a na końcu trudne — z wielkim finałem.
We wszystkich zadaniach sprawdzarka mierzy czas. Przy każdym widać, jakich zagadnień używa — jeśli coś brzmi obco, wróć do odpowiedniej części, mapa lekcji jest na górze strony. A tu masz najważniejsze schematy w jednym miejscu:
Ściąga: gotowe schematy
Liczenie obrotów
od a do b: b - a + 1 co k: (b - a) / k + 1 po kolei: dodajemy w środku: mnożymy i < j: n * (n - 1) / 2
Najpierw sprawdź na małym n z licznikiem ile++, potem ufaj wzorowi.
Logarytm
while (n > 1) n /= 2; // log n for (p = 1; p <= n; p *= 2) 2^10 ≈ 10^3, 2^20 ≈ 10^6 2^30 ≈ 10^9, 2^60 ≈ 10^18
Połowienie: zgadywanie, lower_bound, szybka potęga — najwyżej ok. 60 kroków.
Czy zdąży?
10^8 operacji ≈ 1 s n ≤ 20 O(2^n) n ≤ 500 O(n^3) n ≤ 5000 O(n^2) n ≤ 10^6 O(n log n) n ≤ 10^8 O(n) większe O(√n), O(log n), O(1)
Złożoność liczysz dla największych danych z treści.
Generator danych
long long n, s, a, b, m;
cin >> n >> s >> a >> b >> m;
vector<long long> x(n);
x[0] = s;
for (int i = 1; i < n; i++)
x[i] = (x[i-1] * a + b) % m;
Wszystko w long long. Sprawdź przykład z treści na kartce.
Wzory i pierwiastek
(a + b) * (b - a + 1) / 2 n / k // wielokrotności n/3 + n/5 - n/15 // 3 lub 5 for (d = 1; d * d <= n; d++)
Dzielniki, pierwszość, rozkład: O(√n). Pierwiastek: sqrtl i poprawka.
Przygotuj raz
P[i] = P[i-1] + t[i]; suma(l, r) = P[r] - P[l-1]; ile[x]++; // zliczanie d[l] += v; d[r+1] -= v; okno += t[i] - t[i-k];
Q pytań o te same dane: O(n + q) zamiast O(n · q). Pierwsze do n: sito.
Sortuj i szukaj
sort(v.begin(), v.end());
lower_bound(.., a) // pierwszy >= a
upper_bound(.., b) // pierwszy > b
while (l < r) { … l++ / r-- }
Ile w [a, b]: upper − lower. Para o sumie k i okna: dwa wskaźniki, O(n).
Połowienie po odpowiedzi
while (l < r) {
s = (l + r + 1) / 2;
if (dobre(s)) l = s;
else r = s - 1;
}
Gdy warunek zmienia się z „tak” na „nie” tylko raz. Około 60 kroków dla zakresu 10¹⁸.
long long. 5) Sprawdź program na małym przykładzie z treści, a potem pomyśl o największym teście.
Rozgrzewka · zadania 1–10
Wzory i krótkie pętle: ramka z płytek, kasy w sklepie, kuranty, turniej pucharowy, domek z kart, liczby powyżej średniej, wynik wolnego programu, żarówki na korytarzu, numerowanie stron i wspólne wielokrotności.
Średnie · zadania 11–20
Przygotuj raz i szukaj szybko: k-ta liczba niepodzielna, liczby bliźniacze, liczby z trzema dzielnikami, pary o różnicy k, który okres był cieplejszy, rozkład jazdy, dokładnie k warstw farby, pary z dwóch list, najlepszy fragment i różne czynniki pierwsze.
Trudne · zadania 21–28
Liczby z dzielnikami 2, 3 i 5, najdłuższy fragment bez powtórzeń, fragmenty o sumie zero, maszyny w fabryce, k-ta liczba tabliczki mnożenia, trójkąty z patyków, dzielniki wszystkich liczb do n — a na koniec wielki finał: wyprzedaż.