C++ · Etap 3 · Lekcja 17

Złożoność czasowa — czy Twój program zdąży?

Program może liczyć bezbłędnie, a mimo to dostać zero punktów — bo liczy za wolno. Na olimpiadzie i w naszej sprawdzarce każdy test ma limit czasu, zwykle jedną sekundę. Dlatego zanim napiszesz pierwszą linijkę, warto umieć odpowiedzieć na pytanie: ile pracy wykona mój program dla największych danych z treści? W tej lekcji nauczysz się liczyć obroty pętli — pojedynczych, zagnieżdżonych i takich, które dzielą dane na pół — poznasz notację O i regułę „100 milionów operacji na sekundę”, a potem zbierzesz cały zestaw sposobów na przyspieszanie programów: wzory zamiast pętli, pętlę do pierwiastka, sumy prefiksowe, tablice zliczeń, sortowanie i wyszukiwanie binarne. Po każdej części czekają ćwiczenia — a sprawdzarka mierzy w nich czas.

64 ćwiczenia w trakcie lekcji28 zadań w bazie na koniec92 ze sprawdzarką C++
Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Ten odcinek omawia dokładnie ten temat.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

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.

CZĘŚĆ 01–03

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.

CZĘŚĆ 04–05

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.

CZĘŚĆ 06–07

Szybciej: wzory i tablice

Wzór zamiast pętli, pierwiastek zamiast n, sumy prefiksowe, tablice zliczeń, sito i tablica różnic.

CZĘŚĆ 08

Sortuj i szukaj

Sortowanie raz, a potem lower_bound w O(log n), dwa wskaźniki i wyszukiwanie binarne po odpowiedzi.

W tej lekcji sprawdzarka mierzy czas Każdy test ma limit czasu — zwykle 1 sekundę. Program, który liczy poprawnie, ale za wolno, dostaje werdykt Time limit exceeded (przekroczony limit czasu), a sprawdzarka pomija wtedy pozostałe testy. W wielu ćwiczeniach z tej lekcji „najprostszy” pomysł przejdzie małe testy i zatrzyma się na dużych — dokładnie o to chodzi. Gdy zobaczysz TLE, nie szukaj literówki: policz obroty i poszukaj szybszego pomysłu. Złota zasada zostaje: wypisuj dokładnie to, o co prosi zadanie.

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.

jedna_petla.cpp
long long n = 100000, ile = 0;
for (long long i = 1; i <= n; i++) {
    ile++;
}
cout << ile << "\n";
▶ Wyjście
100000
petla_w_petli.cpp
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";
▶ Wyjście (po kilkunastu sekundach)
(nie doczekasz w limicie 1 sekundy)

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ętliile obrotówprzykład
for (i = 1; i <= n; i++)nn = 10 → 10
for (i = 0; i < n; i++)nn = 10 → 10 (od 0 do 9)
for (i = n; i >= 1; i--)nw dół — tyle samo
for (i = a; i <= b; i++)b − a + 1od 3 do 7 → 5
for (i = a; i < b; i++)b − aod 3 do 6 → 4
for (i = a; i <= b; i += k)(b − a) / k + 1od 2 do 20 co 3 → 7
while (x >= k) x -= k;x / kx = 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.

Pętla od 3 do 7 odwiedza 5 liczb — numery pod spodem liczą obroty.
od_a_do_b.cpp
long long a, b;
cin >> a >> b;
long long ile = 0;
if (a <= b) ile = b - a + 1;
cout << ile << "\n";
▶ Wejście 1
3 7
▶ Wyjście 1
5
▶ Wejście 2
-1000000000000000000 1000000000000000000
▶ Wyjście 2
2000000000000000001

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

co_k.cpp
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";
▶ Wyjście
2 5 8 11 14 17 20 7 = 7

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

odejmowanie.cpp
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";
▶ Wejście
17 5
▶ Wyjście
3 2

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

po_kolei.cpp
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";
▶ Wyjście
13

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

if_w_petli.cpp
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";
▶ Wejście
100
▶ Wyjście
100 33 20 100 33 20

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.

Jak liczyć obroty Od a do b włącznie: 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.
Sprawdź się w głowie

Najpierw policz obroty w głowie albo na kartce — bez uruchamiania — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile wypisze ten fragment?
int ile = 0;
for (int i = 5; i <= 12; i++) ile++;
cout << ile;
Pokaż odpowiedź
8Od 5 do 12 włącznie: 12 − 5 + 1 = 8. Nie 7 — pamiętaj o płocie i słupkach.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 5; i < 12; i++) ile++;
cout << ile;
Pokaż odpowiedź
7Ostre <: liczba 12 odpada, zostaje 12 − 5 = 7 obrotów.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 1; i <= 100; i += 10) ile++;
cout << ile;
Pokaż odpowiedź
10Odwiedza 1, 11, 21, …, 91 — (100 − 1) / 10 + 1 = 9 + 1 = 10 obrotów. Następna byłaby 101.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 10; i >= 1; i -= 2) ile++;
cout << ile;
Pokaż odpowiedź
510, 8, 6, 4, 2 — pięć obrotów. Liczba 0 nie spełnia już warunku i >= 1.
Ile wypisze ten fragment?
int x = 100, ile = 0;
while (x >= 7) { x -= 7; ile++; }
cout << ile << " " << x;
Pokaż odpowiedź
14 2Pętla dzieli powoli: 100 / 7 = 14 odejmowań, reszta 100 % 7 = 2.
Ile wypisze ten fragment?
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ź
16Pętle po kolei — dodajemy: 6 + 6 + 4 = 16.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 1; i <= 30; i++)
    if (i % 4 == 0) ile++;
cout << ile;
Pokaż odpowiedź
7Pętla robi 30 obrotów, ale ile++ wykonuje się tylko dla 4, 8, …, 28 — 30 / 4 = 7 razy.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 20; i <= 10; i++) ile++;
cout << ile;
Pokaż odpowiedź
0Start 20 nie spełnia warunku i <= 10 — pętla nie wykona się ani razu. Wzór 10 − 20 + 1 dałby −9, dlatego ten przypadek sprawdzamy osobno.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

1.1 Ile obrotów od a do b?łatwe✓ zaliczone Ile razy wykona się for (i = a; i <= b; i++)? Liczby sięgają tryliona — pętla nie zdąży, policz wzorem. b − a + 1a > b daje 0long long Rozwiąż 1.2 Co k krokówłatwe✓ zaliczone Ile obrotów zrobi for (i = a; i <= b; i += k)? Odległość podziel przez krok i dodaj pierwszy obrót. (b − a) / k + 1dzielenie całkowitelong long Rozwiąż 1.3 Odejmowanie zamiast dzieleniałatwe✓ zaliczone Pętla odejmuje k od x, dopóki się da. Ile razy odejmie i co zostanie? To zwykłe / i %. x / kx % kpętla zastąpiona działaniem Rozwiąż 1.4 Gdzie skończy pętla?łatwe✓ zaliczone Ostatnia wartość i w pętli co k i wartość i po wyjściu z pętli — bez wykonywania pętli. liczba obrotówa + k · ilelong long Rozwiąż 1.5 if w pętliłatwe✓ zaliczone Ile razy wykona się instrukcja pod if (i % a == 0), a ile pod else? Pętla idzie do 10¹⁸. n / aif w pętlipolicz zamiast wykonywać Rozwiąż 1.6 Wielokrotności w przedzialełatwe✓ zaliczone Ile wielokrotności k leży między a i b? Tyle, ile do b, minus tyle, ile do a − 1. b / k − (a − 1) / kbez pętlilong long Rozwiąż 1.7 Pościgśrednie✓ zaliczone Bartek ma d metrów przewagi, Ala biegnie szybciej. Po ilu minutach go dogoni? Symulacja minuta po minucie nie zdąży. dzielenie w góręróżnica prędkościlong long Rozwiąż 1.8 Pętla z dwiema zmiennymiśrednie✓ zaliczone a rośnie o p, b maleje o q, dopóki a < b. Ile obrotów i jakie wartości na końcu? dzielenie w górędwie zmiennepolicz zamiast symulować Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

tabliczka.cpp
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";
▶ Wyjście
1 2 3 4 2 4 6 8 3 6 9 12 obrotow: 12

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.

Pętla w pętli — każde pole to jeden obrót

        
Ta ramka działa po włączeniu JavaScriptu.
wewnętrzna pętlaobrotów razemn = 5
j = 1 … nn · n25
j = i + 1 … nn · (n − 1) / 210
j = 1 … in · (n + 1) / 215
j = 1 … i − 1n · (n − 1) / 210

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

gauss.cpp
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";
▶ Wejście 1
10
▶ Wyjście 1
55 55
▶ Wejście 2
100000
▶ Wyjście 2
5000050000 5000050000

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

trojki.cpp
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";
▶ Wyjście
216 20 216 20

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

litery.cpp
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";
▶ Wyjście
10

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

Pętle zagnieżdżone Pętla w pętli: 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łą.
Sprawdź się w głowie

Najpierw policz obroty na kartce — narysuj sobie kratkę, jeśli pomaga — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile wypisze ten fragment?
int ile = 0;
for (int i = 0; i < 4; i++)
    for (int j = 0; j < 7; j++) ile++;
cout << ile;
Pokaż odpowiedź
28Pętla w pętli — mnożymy: 4 · 7 = 28.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 0; i < 4; i++) ile++;
for (int j = 0; j < 7; j++) ile++;
cout << ile;
Pokaż odpowiedź
11Pętle po kolei — dodajemy: 4 + 7 = 11.
Ile wypisze ten fragment?
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ź
28Pary i < j: 8 · 7 / 2 = 28 — tyle meczów w turnieju 8 drużyn.
Ile wypisze ten fragment?
int n = 8, ile = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) ile++;
cout << ile;
Pokaż odpowiedź
36Schodki 1 + 2 + … + 8 = 8 · 9 / 2 = 36.
Ile wypisze ten fragment?
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ź
125Trzy pętle po 5: 5³ = 125.
Ile wypisze ten fragment?
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ź
50W każdym z 10 obrotów zewnętrznej pętli dwie wewnętrzne stoją po kolei: 3 + 2 = 5. Razem 10 · 5 = 50.
Ile wypisze ten fragment?
long long n = 100000;
cout << n * (n - 1) / 2;
Pokaż odpowiedź
4999950000Tyle par i < j ma 100 000 elementów — prawie 5 miliardów. Sprawdzanie każdej pary trwałoby kilkadziesiąt sekund.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 1; i <= 6; i++)
    for (int j = i; j <= 6; j += 2) ile++;
cout << ile;
Pokaż odpowiedź
12Dla i = 1: j = 1, 3, 5 (3 obroty); i = 2: 2, 4, 6 (3); i = 3: 3, 5 (2); i = 4: 4, 6 (2); i = 5: 5 (1); i = 6: 6 (1). Razem 12.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

2.1 Wielka tabliczka mnożeniałatwe✓ zaliczone Ile razy wykona się ciało pętli w pętli dla n wierszy i m kolumn? Liczby sięgają trzech miliardów. n · mpętla w pętlilong long Rozwiąż 2.2 Każdy z każdymłatwe✓ zaliczone Turniej n drużyn, każda gra z każdą raz. Ile meczów? Pętla j od i + 1 — wzór n(n − 1)/2. pary i < jn · (n − 1) / 2long long Rozwiąż 2.3 Schodki z gwiazdekłatwe✓ zaliczone Trójkąt z n wierszy: w i-tym wierszu i gwiazdek. Ile gwiazdek razem? Suma Gaussa. n · (n + 1) / 2j od 1 do ilong long Rozwiąż 2.4 Po kolei i w środkułatwe✓ zaliczone Trzy fragmenty: pętla po n, pętla w pętli n × m, pętla po m. Ile obrotów robi każdy i ile razem? dodawanie i mnożenien + n · m + mlong long Rozwiąż 2.5 Trójki bez powtórzeńśrednie✓ zaliczone Ile obrotów zrobią trzy pętle i < j < k? To „wybierz 3 z n” — uważaj na kolejność dzielenia. n(n − 1)(n − 2) / 6trzy pętleprzepełnienie Rozwiąż 2.6 Kwadraty w kratceśrednie✓ zaliczone Ile kwadratów każdej wielkości mieści się w kratce n × n? Policz według wielkości boku. suma kwadratówn(n + 1)(2n + 1) / 6long long Rozwiąż 2.7 Prostokąty w kratceśrednie✓ zaliczone Ile prostokątów (o bokach wzdłuż linii) mieści się w kratce n × m? Wybierz dwie linie pionowe i dwie poziome. pary liniiiloczyn wzorówlong long Rozwiąż 2.8 Pętla z krokiem iśrednie✓ zaliczone Wewnętrzna pętla skacze co i: for (j = i; j <= n; j += i). Ile obrotów razem? Około n · ln n. n / isuma po iO(n log n) Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

polowienie.cpp
long long n;
cin >> n;
int ile = 0;
while (n > 1) {
    n /= 2;
    ile++;
}
cout << ile << "\n";
▶ Wejście 1
1000
▶ Wyjście 1
9
▶ Wejście 2
1000000000000000000
▶ Wyjście 2
59
obrótn po dzieleniu
1500
2250
3125
462
531
615
77
83
91

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ół

nmniej więcejlog₂ n
2¹⁰ = 1024tysiąc (10³)10
2²⁰ = 1 048 576milion (10⁶)20
2³⁰ = 1 073 741 824miliard (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

podwajanie.cpp
long long n;
cin >> n;
int ile = 0;
for (long long p = 1; p <= n; p *= 2) {
    cout << p << " ";
    ile++;
}
cout << "\n" << ile << "\n";
▶ Wejście
100
▶ Wyjście
1 2 4 8 16 32 64 7

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

Zgadnij liczbę — po każdym pytaniu połowa odpada
Ta ramka działa po włączeniu JavaScriptu.
zgadywanie.cpp
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";
▶ Wejście 1
1000000 777777
▶ Wyjście 1
777777 po 20 pytaniach
▶ Wejście 2
1000000000000000000 1
▶ Wyjście 2
1 po 60 pytaniach

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

szybka_potega.cpp
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";
▶ Wejście
2 1000000000000000000 1000000007
▶ Wyjście
719476260 (60 krokow)

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

Logarytm w praktyce Pętla, która w każdym obrocie dzieli coś przez 2 (albo podwaja licznik), robi około 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.
Sprawdź się w głowie

Najpierw policz obroty w głowie — pomaga pamiętać, że 2¹⁰ to około tysiąc — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile wypisze ten fragment?
int n = 64, ile = 0;
while (n > 1) { n /= 2; ile++; }
cout << ile;
Pokaż odpowiedź
664 → 32 → 16 → 8 → 4 → 2 → 1: sześć dzieleń, bo 64 = 2⁶.
Ile wypisze ten fragment?
int n = 100, ile = 0;
while (n > 1) { n /= 2; ile++; }
cout << ile;
Pokaż odpowiedź
6100 → 50 → 25 → 12 → 6 → 3 → 1: sześć obrotów (dzielenie całkowite ucina połówki).
Ile wypisze ten fragment?
int ile = 0;
for (int p = 1; p <= 1000; p *= 2) ile++;
cout << ile;
Pokaż odpowiedź
10p = 1, 2, 4, …, 512 — dziesięć potęg dwójki nie większych od 1000 (następna to 1024).
Ile wypisze ten fragment?
long long n = 1000000000, ile = 0;
while (n > 0) { n /= 10; ile++; }
cout << ile;
Pokaż odpowiedź
10Dzielenie przez 10 odcina cyfry — miliard ma 10 cyfr, więc 10 obrotów.
Ile wypisze ten fragment?
int ile = 0;
for (int p = 1; p <= 1000; p *= 3) ile++;
cout << ile;
Pokaż odpowiedź
71, 3, 9, 27, 81, 243, 729 — siedem obrotów. Mnożenie przez 3 to logarytm przy podstawie 3.
Ile wypisze ten fragment?
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ź
20Zgadywanie w zakresie miliona zawsze kończy się po około 20 pytaniach — tu dokładnie 20.
Ile wypisze ten fragment?
int ile = 0;
for (int i = 1; i <= 8; i++)
    for (int p = 1; p <= 8; p *= 2) ile++;
cout << ile;
Pokaż odpowiedź
32Zewnętrzna pętla: 8 obrotów. Wewnętrzna: p = 1, 2, 4, 8 — 4 obroty. Razem 8 · 4 = 32, czyli n · (log₂ n + 1).
Ile wypisze ten fragment?
long long b = 1000000, kroki = 0;
while (b > 0) { b /= 2; kroki++; }
cout << kroki;
Pokaż odpowiedź
20Tyle kroków robi szybkie potęgowanie dla wykładnika miliona: milion da się dzielić na pół 20 razy, zanim zostanie 0.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

3.1 Ile razy na pół?łatwe✓ zaliczone Ile razy można podzielić n przez 2 (całkowicie), zanim zostanie 1? Nawet dla 10¹⁸ to najwyżej 59 kroków. n /= 2log₂ npętla jest szybka Rozwiąż 3.2 Potęgi dwójki do nłatwe✓ zaliczone Ile obrotów zrobi for (p = 1; p <= n; p *= 2)? Uważaj, żeby licznik się nie przepełnił. p *= 2log₂ n + 1long long Rozwiąż 3.3 Cyfry w innym systemiełatwe✓ zaliczone Ile cyfr ma liczba n zapisana w systemie o podstawie b? Dziel przez b, dopóki coś zostaje. n /= blogarytm o podstawie bzero ma jedną cyfrę Rozwiąż 3.4 Ile pytań w zgadywance?łatwe✓ zaliczone Ile pytań „czy większa od…?” trzeba w najgorszym razie, żeby odgadnąć liczbę od 1 do n? połowienie przedziałunajmniejsze k z 2ᵏ ≥ nlong long Rozwiąż 3.5 Kartka do Księżycałatwe✓ zaliczone Kartka ma 0,1 mm grubości, a każde złożenie ją podwaja. Ile złożeń, żeby sięgnąć d milimetrów? podwajanieliczby całkowite zamiast 0,1logarytm Rozwiąż 3.6 Zgadywanie krok po krokuśrednie✓ zaliczone Dla każdej sekretnej liczby policz, ile pytań zada strategia „pytaj o środek”. Każde zgadywanie to ok. 60 kroków. wyszukiwanie binarnel, r i środeklong long Rozwiąż 3.7 Kolonia bakteriiśrednie✓ zaliczone Co godzinę bakterii jest k razy więcej. Po ilu godzinach z a zrobi się co najmniej b? Uważaj na przepełnienie. mnożenie przez klogarytm o podstawie ksprawdź przed mnożeniem Rozwiąż 3.8 Do kwadratu, do kwadratu…średnie✓ zaliczone Ile razy można podnieść x do kwadratu, nie przekraczając n? Nawet dla 10¹⁸ to najwyżej kilka kroków. x = x * xlog log nsprawdź przed mnożeniem Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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ówzłożonośćdlaczego
3n + 100O(n)stała 3 i +100 odpadają
26 · nO(n)stała 26 odpada
n · (n − 1) / 2O(n²)to n²/2 − n/2
n² + nO(n²)n rośnie wolniej niż n²
n · log₂ n + nO(n log n)n rośnie wolniej
log₂ n + 5O(log n)+5 odpada
1000O(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śćnazwatypowy kodn = 10⁶
O(1)staławzór, v[i], v.size()1
O(log n)logarytmicznapołowienie, lower_bound20
O(√n)pierwiastkowapętla d * d <= n1000
O(n)liniowajedna pętla po danych10⁶
O(n log n)„n log n”sort2 · 10⁷
O(n²)kwadratowapętla w pętli10¹²
O(n³)sześciennatrzy pętle10¹⁸
O(2ⁿ)wykładniczawszystkie podzbiory (maski)liczba o 300 000 cyfrach
O(n!)silniawszystkie permutacjejeszcze 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.

010020030040015101520n — rozmiar danychliczba operacjiO(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)
Liczba operacji dla n od 1 do 20. Przy dużym n różnice robią się gigantyczne — to tylko sam początek wykresu.

Co się stanie, gdy danych będzie 10 razy więcej?

złożonośćdane × 10czas
O(1)× 10bez 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.

razy_sto.cpp
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";
▶ Wyjście
1000000 100000000 100

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

Czasomierz — ile to potrwa przy 100 milionach operacji na sekundę?
Ta ramka działa po włączeniu JavaScriptu.

Stałe mają znaczenie — ale tylko dla małych n

nprogram A: 1000 · nprogram B: n²szybszy
1010 000100B
100100 00010 000B
100010⁶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ę.

poleceniekosztuwaga
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, reverseO(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 vectoraO(n)tworzą nową kopię całości
lower_bound, binary_search (na posortowanym)O(log n)połowienie
sklejanie_wolno.cpp
string s;
for (int i = 0; i < 1000000; i++) {
    s = s + 'a';     // kopiuje cały napis!
}
cout << s.size() << "\n";
▶ Wyjście (po kilkudziesięciu sekundach)
1000000
sklejanie_szybko.cpp
string s;
for (int i = 0; i < 1000000; i++) {
    s += 'a';        // dopisuje na koniec
}
cout << s.size() << "\n";
▶ Wyjście
1000000

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.

Notacja O w pigułce Zostaw najszybciej rosnący składnik i pomiń stałe: 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ę.
Sprawdź się w głowie

Najpierw odpowiedz w głowie — pomyśl, jak rośnie praca — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile razy więcej obrotów? Co wypisze fragment?
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ź
10Pojedyncza pętla — O(n): dane razy 10, praca razy 10.
A tu?
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ź
9O(n²): dane razy 3, praca razy 3² = 9.
O ile więcej obrotów robi pętla połowiąca dla miliona niż dla tysiąca?
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ź
109 obrotów dla tysiąca, 19 dla miliona. Dane razy tysiąc — tylko 10 obrotów więcej. Tak działa O(log n).
Co wypisze fragment i jaka to złożoność?
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ź
10100n + n² = 100 + 10 000. Składnik n² przeważa, więc to O(n²) — pierwsza pętla prawie nic nie zmienia.
Co wypisze fragment i jaka to złożoność?
int n = 10, ile = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < 26; j++) ile++;
cout << ile;
Pokaż odpowiedź
26026 · n — wewnętrzna pętla ma stałą długość, więc to O(n) ze stałą 26.
Który program robi więcej obrotów: A (1000 · n) czy B (n²)? Fragment wypisuje 1, gdy A.
long long n1 = 100, n2 = 10000;
cout << (1000 * n1 > n1 * n1) << (1000 * n2 > n2 * n2);
Pokaż odpowiedź
10Dla n = 100 więcej robi A (100 000 > 10 000), dla n = 10 000 — już B (10⁸ > 10⁷). Przy dużych danych zawsze wygrywa lepsza złożoność.
Co wypisze fragment?
string s;
for (int i = 0; i < 5; i++) s = s + "ab";
cout << s.size();
Pokaż odpowiedź
10Wynik jest dobry (5 · 2 = 10 liter), ale każde s = s + … kopiuje cały napis. Dla miliona obrotów to O(n²). Pisz s += "ab".
Ile operacji „usuń pierwszy element”? Co wypisze fragment?
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ź
15Usuwanie z początku przesuwa wszystkie pozostałe: 5 + 4 + 3 + 2 + 1 + 0 = 15 = n(n − 1)/2. Opróżnianie vectora od przodu to O(n²).
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

4.1 Najważniejszy składnikłatwe✓ zaliczone Program wykonuje c₃n³ + c₂n² + c₁n + c₀ operacji. Jaka to złożoność? Zostaw najszybciej rosnący składnik. notacja Onajwyższa potęgapomiń stałe Rozwiąż 4.2 Dane razy kłatwe✓ zaliczone Program działał c milisekund. Ile potrwa, gdy danych będzie k razy więcej? Zależy od złożoności. O(n) → × kO(n²) → × k²string i if Rozwiąż 4.3 Od którego n wygrywa liniowy?średnie✓ zaliczone Program A robi a · n operacji, program B — b · n². Od którego n program A jest szybszy? Pętla po n nie zdąży. stałe mają znaczeniea · n < b · n²dzielenie całkowite Rozwiąż 4.4 Tabela wzrostułatwe✓ zaliczone Dla danego n wypisz log n, n, n log n, n², n³ i 2ⁿ — i zobacz na własne oczy, jak różnie rosną. klasy złożoności1LL << nlong long Rozwiąż 4.5 Wielomian czy wykładnicza?średnie✓ zaliczone Co jest większe: nᵏ czy 2ⁿ? Dla małych n bywa różnie, ale 2ⁿ zawsze w końcu wygrywa. nᵏ i 2ⁿpotęgowanie pętląlong long Rozwiąż 4.6 Najtańszy programśrednie✓ zaliczone Trzy programy: a · n², b · n · L i c · n operacji. Który jest najtańszy dla danego n? Stałe mają znaczenie! stała i kształtporównywanie kosztówremis — wcześniejsza litera Rozwiąż 4.7 Usuwanie z początkuśrednie✓ zaliczone Każde v.erase(v.begin()) przesuwa wszystkie pozostałe elementy. Ile przesunięć kosztuje usunięcie k pierwszych? ukryte kosztyerase w pętlisuma kolejnych liczb Rozwiąż 4.8 Połowienie w środku pętlitrudne✓ zaliczone Dla każdego i od 1 do n wewnętrzna pętla dzieli j przez 2. Ile obrotów razem? Pogrupuj liczby według długości. O(n log n)grupy potęg dwójkilong long Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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

ograniczeniewystarczy złożonośćoperacji
n ≤ 10O(n!)3,6 · 10⁶
n ≤ 20O(2ⁿ)10⁶
n ≤ 500O(n³)1,25 · 10⁸
n ≤ 5000O(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.

czy_zdazy.cpp
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";
▶ Wejście 1
5000
▶ Wyjście 1
n^2 = 25000000 - zdazy
▶ Wejście 2
200000
▶ Wyjście 2
n^2 = 40000000000 - za wolno

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.

generator.cpp
#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;
}
▶ Wejście 1
5 3 7 1 10
▶ Wyjście 1
19 6
▶ Wejście 2
1000000 12345 1103515 12345 1000000000
▶ Wyjście 2
499843464215200 996912645

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

rozne_wolno.cpp
// 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ń
▶ Werdykt sprawdzarki
Time limit exceeded
rozne_szybko.cpp
// 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
▶ Werdykt sprawdzarki
Accepted
Zanim napiszesz program 1) Przeczytaj ograniczenia i weź największe n. 2) Policz złożoność swojego pomysłu i wstaw n. 3) Porównaj z 10⁸ na sekundę: do kilkudziesięciu milionów — spokojnie, kilkaset milionów — ryzykownie, miliardy — na pewno nie. 4) Jeśli nie zdąży — szukaj innego pomysłu, zanim zaczniesz pisać. Tabela ograniczeń podpowie, jakiej złożoności szukać.
Sprawdź się w głowie

Najpierw oszacuj w głowie — liczba operacji i reguła 10⁸ na sekundę — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile operacji wykona pętla w pętli dla n = 30 000?
long long n = 30000;
cout << n * n;
Pokaż odpowiedź
9000000009 · 10⁸ — około 9 sekund. Za wolno na limit 1 s.
A sortowanie dla tego samego n? (log₂ 30 000 ≈ 15)
long long n = 30000;
cout << n * 15;
Pokaż odpowiedź
450000Niecałe pół miliona operacji — tysięczne części sekundy. Ta sama wielkość danych, zupełnie inny czas.
Czy trzy pętle po n zdążą dla n = 400? Program wypisze 1, jeśli tak.
long long n = 400;
cout << (n * n * n <= 100000000);
Pokaż odpowiedź
1400³ = 6,4 · 10⁷ — mniej niż 10⁸, więc zdąży.
A dla n = 1000?
long long n = 1000;
cout << (n * n * n <= 100000000);
Pokaż odpowiedź
01000³ = 10⁹ — dziesięć razy za dużo. Dla n ≤ 1000 potrzeba czegoś szybszego niż O(n³).
Ile podzbiorów ma zbiór 20 elementów?
cout << (1 << 20);
Pokaż odpowiedź
10485762²⁰ — około miliona. Przejrzenie wszystkich podzbiorów zdąży. Dla 40 elementów byłby to bilion.
Co wypisze generator dla n = 4, s = 1, a = 2, b = 3, m = 10?
long long x = 1;
cout << x;
for (int i = 2; i <= 4; i++) {
    x = (x * 2 + 3) % 10;
    cout << " " << x;
}
Pokaż odpowiedź
1 5 3 9x₁ = 1, x₂ = (1 · 2 + 3) mod 10 = 5, x₃ = (5 · 2 + 3) mod 10 = 3, x₄ = (3 · 2 + 3) mod 10 = 9.
Co wypisze fragment?
long long x = 3, suma = 3;
for (int i = 2; i <= 5; i++) {
    x = (x * 7 + 1) % 10;
    suma += x;
}
cout << suma;
Pokaż odpowiedź
19Ciąg 3, 2, 5, 6, 3 — suma 19, tak samo jak w pierwszym wejściu generator.cpp.
Ile kroków zrobi pętla do pierwiastka dla n = 10¹²?
long long n = 1000000000000, ile = 0;
for (long long d = 1; d * d <= n; d++) ile++;
cout << ile;
Pokaż odpowiedź
1000000Milion kroków — natychmiast. Pętla do n zrobiłaby bilion, czyli kilka godzin.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

5.1 Czego szuka autor zadania?łatwe✓ zaliczone Z ograniczenia na n odczytaj z tabeli z lekcji, jaka złożoność wystarczy. Ciąg if … else if. tabela ograniczeńif … else iflong long Rozwiąż 5.2 Czy zdąży w sekundę?średnie✓ zaliczone Dla złożoności i n policz operacje i porównaj ze 100 milionami. Uważaj: n³ dla n = 10¹⁸ przepełni long long. 10⁸ operacji na sekundęprzepełnienienajpierw sprawdź, potem mnóż Rozwiąż 5.3 Największe n w budżecieśrednie✓ zaliczone Masz budżet T operacji. Jak duże dane przerobi program O(n), O(n²), O(n³), O(2ⁿ) albo O(n!)? Tabela z lekcji od drugiej strony. tabela od drugiej stronypętla z warunkiemlong long Rozwiąż 5.4 Generator: suma, minimum, maksimumłatwe✓ zaliczone Pierwsze zadanie z danymi z generatora: wygeneruj milion liczb według przepisu z lekcji i policz sumę, najmniejszą i największą. generatorvectorO(n) Rozwiąż 5.5 Ile różnych liczb?średnie✓ zaliczone Milion liczb z generatora, każda mniejsza od m ≤ 10⁶. Ile różnych? Pętla w pętli nie zdąży — zaznaczaj w tablicy. tablica boolO(n + m)generator Rozwiąż 5.6 Najczęstsza liczbaśrednie✓ zaliczone Która liczba z generatora występuje najczęściej? Tablica zliczeń zamiast liczenia od nowa dla każdej liczby. tablica zliczeńO(n + m)remis — najmniejsza Rozwiąż 5.7 Najlepszy zyskśrednie✓ zaliczone Ceny akcji z generatora. Kup jednego dnia, sprzedaj później — jaki największy zysk? Pamiętaj najniższą cenę dotąd. minimum dotądjedno przejścieO(n) Rozwiąż 5.8 Najdłuższa seria wzrostówśrednie✓ zaliczone Najdłuższy spójny fragment ciągu z generatora, w którym każda liczba jest większa od poprzedniej. Jedno przejście. licznik seriiO(n)generator Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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

suma_a_b.cpp
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";
▶ Wejście 1
3 7
▶ Wyjście 1
25
▶ Wejście 2
-1000000000 1000000000
▶ Wyjście 2
0
▶ Wejście 3
1 1000000000
▶ Wyjście 3
500000000500000000

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

wielokrotnosci.cpp
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";
▶ Wejście 1
20 3
▶ Wyjście 1
6 63
▶ Wejście 2
1000000000 7
▶ Wyjście 2
142857142 71428571071428571

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

trzy_lub_piec.cpp
long long n;
cin >> n;
long long wynik = n / 3 + n / 5 - n / 15;
cout << wynik << "\n";
▶ Wejście 1
20
▶ Wyjście 1
9
▶ Wejście 2
1000000000000000000
▶ Wyjście 2
466666666666666667

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

pary_wzor.cpp
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";
▶ Wejście 1
6 7
▶ Wyjście 1
3
▶ Wejście 2
1000000000000 1500000000000
▶ Wyjście 2
250000000000

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

dzielniki.cpp
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";
▶ Wejście 1
36
▶ Wyjście 1
9
▶ Wejście 2
963761198400
▶ Wyjście 2
6720

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)

rozklad.cpp
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";
▶ Wejście 1
360
▶ Wyjście 1
2 2 2 3 3 5
▶ Wejście 2
999999999989
▶ Wyjście 2
999999999989
▶ Wejście 3
600851475143
▶ Wyjście 3
71 839 1471 6857

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ą

kwadraty.cpp
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";
▶ Wejście 1
50
▶ Wyjście 1
7
▶ Wejście 2
999999999999999999
▶ Wyjście 2
999999999

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

Wzory i pierwiastek Suma od a do b: (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.
Sprawdź się w głowie

Najpierw policz w głowie — wzorem, nie pętlą — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze fragment?
long long a = 10, b = 20;
cout << (a + b) * (b - a + 1) / 2;
Pokaż odpowiedź
165Liczb od 10 do 20 jest 11, a para pierwsza + ostatnia daje 30: 30 · 11 / 2 = 165.
Ile wielokrotności 7 jest od 1 do 100?
cout << 100 / 7;
Pokaż odpowiedź
147, 14, …, 98 — czternaście liczb.
Ile wielokrotności 7 jest od 50 do 100?
long long a = 50, b = 100, k = 7;
cout << b / k - (a - 1) / k;
Pokaż odpowiedź
7Do 100 jest ich 14, do 49 — 7 (bo 49 = 7 · 7). Zostaje 14 − 7 = 7: od 56 do 98.
Ile liczb od 1 do 30 dzieli się przez 2 lub przez 3?
long long n = 30;
cout << n / 2 + n / 3 - n / 6;
Pokaż odpowiedź
2015 parzystych + 10 podzielnych przez 3 − 5 podzielnych przez 6 (policzonych dwa razy) = 20.
Ile obrotów zrobi pętla do pierwiastka dla n = 10 000?
long long n = 10000, ile = 0;
for (long long d = 1; d * d <= n; d++) ile++;
cout << ile;
Pokaż odpowiedź
100d dochodzi do 100, bo 100 · 100 = 10 000. Pętla do n zrobiłaby 10 000 obrotów — sto razy więcej.
Ile dzielników ma 100?
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ź
9Pary: (1, 100), (2, 50), (4, 25), (5, 20) i (10, 10) — ta ostatnia liczy się raz. 4 · 2 + 1 = 9.
Co wypisze fragment?
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ź
2 2 3 784 = 2 · 2 · 3 · 7. Po podzieleniu przez 2, 2 i 3 zostaje 7 — pętla kończy się, bo 3 · 3 > 7, a 7 > 1 wypisujemy na końcu.
Ile par a < b z liczb od 1 do 10 ma sumę 15?
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ź
3a od 5 do 7: pary (5, 10), (6, 9), (7, 8). Mniejszego a nie ma, bo b przekroczyłoby 10.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

6.1 Suma od a do błatwe✓ zaliczone Suma wszystkich liczb całkowitych od a do b — sztuczką Gaussa, bez pętli. Liczby mogą być ujemne. (a + b) · ile / 2liczby ujemnelong long Rozwiąż 6.2 Wielokrotności i ich sumałatwe✓ zaliczone Ile jest wielokrotności k nie większych od n i ile wynosi ich suma? Wyciągnij k przed nawias. n / kk · m(m + 1) / 2long long Rozwiąż 6.3 Ani przez 2, ani przez 3, ani przez 5średnie✓ zaliczone Ile liczb od 1 do n dzieli się przez 2, 3 lub 5, a ile przez żadną z nich? Włączanie i wyłączanie dla trzech liczb. włączanie i wyłączanien / 30long long Rozwiąż 6.4 Pary o sumie s w przedzialeśrednie✓ zaliczone Ile jest par lo ≤ a < b ≤ hi o sumie s? Dobre a tworzą przedział — policz jego długość, bez pętli. przedział dobrych amax i dzielenieO(1) Rozwiąż 6.5 Kwadraty w przedzialeśrednie✓ zaliczone Ile kwadratów liczb całkowitych leży między a i b? Pierwiastek z poprawką — dwa razy. sqrtl i poprawkado b minus do a − 1long long Rozwiąż 6.6 Doskonała, obfita czy deficytowa?średnie✓ zaliczone Suma dzielników właściwych liczby do 10¹² — pętla do pierwiastka, dzielniki parami. dzielniki paramiO(√n)long long Rozwiąż 6.7 Największy czynnik pierwszyśrednie✓ zaliczone Rozłóż liczbę do 10¹² na czynniki w O(√n): wypisz jej największy czynnik pierwszy i liczbę różnych czynników. rozkład na czynnikip * p <= nzostała liczba pierwsza Rozwiąż 6.8 Wspólne dzielnikiśrednie✓ zaliczone Ile dzielników mają wspólnych liczby a i b? NWD z lekcji o modulo, a potem dzielniki parami. NWDdzielniki paramiO(√n) Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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:

suma(l, r) = P[r] − P[l − 1]

Tablicę P liczy jedna pętla: P[i] = P[i - 1] + t[i].

Suma na przedziale z sum prefiksowych
Ta ramka działa po włączeniu JavaScriptu.
prefiksy.cpp
#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;
}
▶ Wejście
8 3 3 1 4 1 5 9 2 6 3 6 1 8 5 5
▶ Wyjście
19 31 5

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)

zliczanie.cpp
// 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

sito.cpp
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";
▶ Wejście 1
100
▶ Wyjście 1
25
▶ Wejście 2
10000000
▶ Wyjście 2
664579

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)

tablica_roznic.cpp
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";
▶ Wejście
6 3 1 3 5 2 6 1 4 4 10
▶ Wyjście
5 6 6 11 1 1

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

okno.cpp
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";
▶ Wyjście
17

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.

Przygotuj raz, pytaj szybko Sumy przedziałów: 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ą.
Sprawdź się w głowie

Najpierw policz w głowie — wypisz sobie tablicę P albo d na kartce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze fragment?
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ź
16Suma od pozycji 2 do 4: 7 + 1 + 8 = 16. P[4] = 18, P[1] = 2.
Co wypisze fragment?
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ź
20Cała tablica: P[5] − P[0] = 20 − 0. Dlatego P[0] = 0 jest potrzebne.
Ile pytań o sumę przedziału obsłuży program w czasie jednego przejścia pętlą po 10⁶ liczbach?
long long n = 1000000;
cout << n;
Pokaż odpowiedź
1000000Bez sum prefiksowych jedno pytanie to do n kroków. Z sumami prefiksowymi — 1 krok. W czasie jednego „ręcznego” liczenia odpowiesz na milion pytań.
Co wypisze fragment?
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ź
3 1 0Czwórki wystąpiły trzy razy, dwójka raz, zera nie ma wcale.
Co wypisze fragment?
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ź
1 6 6 5 0Pozycja 1: +1. Pozycje 2 i 3: +5 i +1. Pozycja 4: tylko +5. Pozycja 5: nic.
Co wypisze fragment?
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ź
10Okna dwóch liczb: 9, 8, 9, 10, 10. Największa suma to 10.
Ile liczb pierwszych jest do 30? (sito)
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ź
102, 3, 5, 7, 11, 13, 17, 19, 23, 29 — dziesięć liczb pierwszych.
Ile kroków wykona program bez sum prefiksowych dla n = 1000 liczb i q = 1000 pytań o cały ciąg?
long long n = 1000, q = 1000;
cout << n * q << " " << n + q;
Pokaż odpowiedź
1000000 2000Ręczne liczenie: n · q = milion kroków. Z sumami prefiksowymi: n + q = 2000. Przy n = q = 10⁶ różnica to 10¹² kontra 2 · 10⁶.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

7.1 Największa suma przedziałułatwe✓ zaliczone Milion liczb i 5000 pytań o sumy przedziałów. Sumy prefiksowe: każde pytanie jednym odejmowaniem. sumy prefiksoweP[r] − P[l − 1]O(n + q) Rozwiąż 7.2 Ile razy wystąpiła?łatwe✓ zaliczone Milion liczb z generatora i 3000 pytań „ile razy wystąpiła liczba v?”. Tablica zliczeń — odpowiedź w O(1). tablica zliczeńv może być ≥ mO(n + m + q) Rozwiąż 7.3 Przewaga parzystychśrednie✓ zaliczone W ilu przedziałach liczb parzystych jest więcej niż nieparzystych? Prefiksowe liczniki parzystych. prefiksy licznikówdługość − parzysteO(n + q) Rozwiąż 7.4 Liczby pierwsze w przedziałachśrednie✓ zaliczone 3000 pytań „ile liczb pierwszych jest od a do b?” dla liczb do 10⁷. Sito raz, potem sumy prefiksowe. sito Eratostenesasumy prefiksowepolicz raz Rozwiąż 7.5 Malowanie płotuśrednie✓ zaliczone Płot z miliona desek i 5000 malowań przedziałów. Tablica różnic: każde malowanie w O(1), na koniec jedno przejście. tablica różnicsuma bieżącaO(n + q) Rozwiąż 7.6 Najlepsze k wyrazów z rzędułatwe✓ zaliczone Największa suma k kolejnych wyrazów ciągu z generatora. Przesuwaj okno: dodaj nowy, odejmij stary. okno stałej długościO(n)pierwsze najlepsze okno Rozwiąż 7.7 Najmniejsza brakująca liczbaśrednie✓ zaliczone Jaka jest najmniejsza liczba całkowita ≥ 0, której nie ma w ciągu? Zaznaczaj w tablicy tylko liczby do n. tablica booltylko liczby ≤ nO(n) Rozwiąż 7.8 Pary o sumie podzielnej przez ktrudne✓ zaliczone Ile jest par wyrazów, których suma dzieli się przez k? Zlicz reszty z dzielenia — reszta r łączy się z k − r. zliczanie resztpary z grupO(n + k) Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

Wyszukiwanie binarne — lower_bound krok po kroku
Ta ramka działa po włączeniu JavaScriptu.
pytania.cpp
#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;
}
▶ Wejście
8 3 15 3 9 27 9 1 20 12 5 15 10 10 -5 100
▶ Wyjście
4 0 8

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)

dwa_wskazniki.cpp
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";
▶ Wyjście
3 + 11

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

okno_zmienne.cpp
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";
▶ Wyjście
4

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

pierwiastek_binarnie.cpp
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";
▶ Wejście 1
50
▶ Wyjście 1
7
▶ Wejście 2
1000000000000000000
▶ Wyjście 2
1000000000

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.

Sortuj i szukaj Sortowanie raz: O(n log n). Potem każde pytanie o liczbę lub przedział: 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).
Sprawdź się w głowie

Najpierw odpowiedz w głowie — wypisz sobie posortowany ciąg — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze fragment?
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ź
2Po sortowaniu: 1 2 4 4 7 9. Pierwsza liczba nie mniejsza od 4 stoi na pozycji 2.
Co wypisze fragment?
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ź
2Różnica strzałek to liczba czwórek: dwie.
Ile liczb jest w przedziale [3, 8]?
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ź
4Po sortowaniu: 1 2 3 5 8 8 10. W [3, 8] są 3, 5, 8, 8 — cztery liczby.
Ile kroków wystarczy, żeby lower_bound znalazł miejsce w ciągu miliona liczb?
int n = 1000000, kroki = 0;
while (n > 1) { n = (n + 1) / 2; kroki++; }
cout << kroki;
Pokaż odpowiedź
20Każdy krok połowi przedział — dla miliona elementów 20 kroków.
Co wypisze fragment? (dwa wskaźniki)
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ź
2 71 + 11 = 12 za dużo (r--), 1 + 7 = 8 za mało (l++), 2 + 7 = 9 — jest.
Ile razy łącznie wykona się „suma -= t[l]” dla n = 8 liczb?
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ź
6Lewy wskaźnik przesuwa się najwyżej n razy w całym programie — tu 6 razy. Pętla w pętli, a pracy O(n).
Co wypisze fragment? (wyszukiwanie po odpowiedzi)
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ź
10Największe x z x³ ≤ 1000 to 10 — pierwiastek sześcienny znaleziony połowieniem.
Ile kroków zrobi takie wyszukiwanie dla zakresu od 0 do 2 · 10⁹?
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ź
30Zakres ma około 2 · 10⁹ ≈ 2³¹ liczb, więc połowień jest najwyżej 31 — tu wystarczyło 30.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

8.1 Czy jest na liście?łatwe✓ zaliczone Milion liczb do 10⁹ i 5000 pytań „czy v jest w ciągu?”. Posortuj raz, potem binary_search. sortbinary_searchO((n + q) log n) Rozwiąż 8.2 Ile mniejszych?średnie✓ zaliczone Dla każdego pytania v policz, ile wyrazów jest mniejszych od v. Pozycja z lower_bound to właśnie odpowiedź. lower_boundpozycja = ile mniejszychsort raz Rozwiąż 8.3 Ile w przedziale wartości?średnie✓ zaliczone Ile wyrazów ciągu ma wartość od lo do hi? Różnica dwóch wyszukiwań: upper_bound minus lower_bound. upper_bound − lower_boundsort razO(log n) na pytanie Rozwiąż 8.4 Najmniejsza różnicaśrednie✓ zaliczone Które dwa wyrazy są najbliżej siebie? Po posortowaniu wystarczy porównać sąsiadów. sortsąsiedziO(n log n) Rozwiąż 8.5 Pary o sumie co najwyżej Sśrednie✓ zaliczone Ile par wyrazów ma sumę ≤ S? Dwa wskaźniki na posortowanym ciągu — jeden z lewej, drugi z prawej. dwa wskaźnikisortO(n log n) Rozwiąż 8.6 Najdłuższy fragment o sumie ≤ Sśrednie✓ zaliczone Najdłuższy spójny fragment ciągu z sumą nie większą niż S. Okno o zmiennej długości — dwa wskaźniki. okno zmiennej długościdwa wskaźnikiO(n) Rozwiąż 8.7 Pierwiastek sześcienny bez pomyłekśrednie✓ zaliczone Największe k, dla którego k³ ≤ n, dla n do 10¹⁸. Wyszukiwanie binarne po odpowiedzi — około 20 kroków. wyszukiwanie binarne po odpowiedzis · s · s ≤ nlong long Rozwiąż 8.8 Wspólne liczby dwóch listśrednie✓ zaliczone Dwie listy po pół miliona liczb. Ile różnych liczb występuje w obu? Posortuj obie i idź dwoma wskaźnikami. sortscalanie dwóch listO(n log n) Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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¹⁸.

Jak rozwiązywać zadania na czas 1) Przeczytaj ograniczenia i z tabeli odczytaj, jakiej złożoności szuka zadanie. 2) Wymyśl najprostsze poprawne rozwiązanie i policz jego obroty dla największych danych. 3) Jeśli nie zdąży, poszukaj powtarzanej pracy: czy pętlę da się zastąpić wzorem? czy można policzyć coś raz (sumy prefiksowe, zliczanie, sito)? czy pomoże sortowanie i połowienie? czy dwa wskaźniki zastąpią parę pętli? 4) Pilnuj typów — duże liczby obrotów to zwykle też duże wyniki: long long. 5) Sprawdź program na małym przykładzie z treści, a potem pomyśl o największym teście.
łatwe

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.

1 Ramka z płytekłatwe✓ zaliczone Podłoga n × m: ile płytek leży przy brzegu, a ile w środku? Wzór zamiast liczenia płytek po kolei. prostokąt w środkujeden wiersz to pułapkalong long Rozwiąż 2 Kasy w sklepiełatwe✓ zaliczone n klientów, k kas, każdy klient to c minut. Kiedy wszyscy będą obsłużeni? Dzielenie z zaokrągleniem w górę. dzielenie w górę(n + k − 1) / klong long Rozwiąż 3 Kurantyłatwe✓ zaliczone Zegar o każdej pełnej godzinie wybija tyle uderzeń, która jest godzina. Ile uderzeń przez h godzin? Co 12 godzin wszystko się powtarza. okres 12 godzin1 + 2 + … + 12 = 78long long Rozwiąż 4 Turniej pucharowyłatwe✓ zaliczone n zawodników, przegrany odpada. Ile meczów i ile rund? Mecze bez pętli, rundy — pętlą z połowieniem. n − 1 meczówpołowienie w góręlogarytm Rozwiąż 5 Domek z kartłatwe✓ zaliczone Ile kart potrzeba na domek z k pięter? Daszki i poziome karty — dwie sumy Gaussa. suma Gaussak(3k + 1) / 2long long Rozwiąż 6 Powyżej średniejłatwe✓ zaliczone Ile liczb z generatora jest większych od średniej? Dwa przejścia i mnożenie zamiast dzielenia. dwa przejściax · n > sumabez liczb z przecinkiem Rozwiąż 7 Wynik wolnego programułatwe✓ zaliczone Program z pętlą w pętli liczy pary o parzystej sumie. Wypisz to samo w O(n): wystarczy policzyć parzyste i nieparzyste. parzystość sumyp · (p − 1) / 2O(n) zamiast O(n²) Rozwiąż 8 Żarówki na korytarzułatwe✓ zaliczone n żarówek, n osób, każda przełącza wielokrotności swojego numeru. Ile świeci na końcu? Wystarczy pierwiastek. dzielniki paramikwadratypierwiastek z poprawką Rozwiąż 9 Numerowanie stronłatwe✓ zaliczone Ile cyfr trzeba wydrukować, żeby ponumerować strony od 1 do n? Pogrupuj strony według liczby cyfr. grupy 1–9, 10–99, …potęgi dziesiątkilong long Rozwiąż 10 Wspólne wielokrotnościłatwe✓ zaliczone Ile liczb od 1 do n dzieli się i przez a, i przez b? NWW z lekcji o modulo — uważaj, żeby się nie przepełniła. NWW = a / NWD · bprzepełnienien / NWW Rozwiąż
średnie

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

11 k-ta liczba niepodzielna przez pśrednie✓ zaliczone Wypisz k-tą dodatnią liczbę, która nie dzieli się przez p. Grupy po p liczb — wzór w O(1). grupy po p liczbk + (k − 1) / (p − 1)long long Rozwiąż 12 Liczby pierwsze bliźniacześrednie✓ zaliczone Ile par liczb pierwszych (p, p + 2) mieści się do n? 3000 pytań do 10⁷ — sito i tablica prefiksowa. sito Eratostenesapary p, p + 2policz raz Rozwiąż 13 Liczby z trzema dzielnikamiśrednie✓ zaliczone Ile liczb do n ma dokładnie trzy dzielniki? To kwadraty liczb pierwszych — sito do miliona i pierwiastek. kwadraty liczb pierwszychsito do √npierwiastek z poprawką Rozwiąż 14 Pary o różnicy kśrednie✓ zaliczone Ile par wyrazów różni się dokładnie o k? Tablica zliczeń: każda wartość v łączy się z v + k. tablica zliczeńile[v] · ile[v + k]O(n + m) Rozwiąż 15 Który okres był cieplejszy?średnie✓ zaliczone Porównaj średnie temperatury dwóch okresów — sumy prefiksowe i mnożenie na krzyż zamiast dzielenia. sumy prefiksowemnożenie na krzyżbez liczb z przecinkiem Rozwiąż 16 Rozkład jazdyśrednie✓ zaliczone Autobusy odjeżdżają o różnych porach, pasażerowie przychodzą na przystanek. Ile łącznie czekają? Sort i lower_bound. sortlower_boundsuma czekania Rozwiąż 17 Dokładnie k warstwśrednie✓ zaliczone Po 5000 malowaniach płotu odpowiedz, ile desek ma dokładnie k warstw. Tablica różnic, a potem tablica zliczeń. tablica różnictablica zliczeńO(n + q + p) Rozwiąż 18 Pary z dwóch listśrednie✓ zaliczone Ile par (liczba z pierwszej listy i liczba z drugiej) ma sumę ≤ S? Posortuj obie listy i idź dwoma wskaźnikami. sortdwa wskaźnikiO(n log n) Rozwiąż 19 Najlepszy fragmentśrednie✓ zaliczone Największa suma spójnego fragmentu ciągu z liczbami ujemnymi. To „najlepszy zysk” na sumach prefiksowych. sumy prefiksoweminimum dotądO(n) Rozwiąż 20 Ile różnych czynników pierwszych?średnie✓ zaliczone Dla każdej liczby do 10⁷ policz różne czynniki pierwsze — sitem, nie rozkładem każdej liczby osobno. sitoliczba pierwsza odwiedza wielokrotnościO(n log log n) Rozwiąż
trudne

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

21 Liczby z dzielnikami 2, 3 i 5trudne✓ zaliczone Ile liczb do n nie ma innych czynników pierwszych niż 2, 3 i 5? Trzy pętle po potęgach — około 11 tysięcy obrotów nawet dla 10¹⁸. potęgi 2, 3 i 5trzy pętlep <= n / 5 Rozwiąż 22 Najdłuższy fragment bez powtórzeńtrudne✓ zaliczone Najdłuższy spójny fragment, w którym żadna liczba się nie powtarza. Okno z dwoma wskaźnikami i tablica liczników. dwa wskaźnikitablica licznikówO(n + m) Rozwiąż 23 Fragmenty o sumie zerotrudne✓ zaliczone Ile spójnych fragmentów ma sumę 0? Taki fragment to dwie równe sumy prefiksowe — posortuj je i policz pary. sumy prefiksowesortpary równych Rozwiąż 24 Maszyny w fabrycetrudne✓ zaliczone n maszyn, każda robi jedną sztukę co tᵢ sekund. Po jakim czasie będzie k sztuk? Wyszukiwanie binarne po odpowiedzi. wyszukiwanie binarne po odpowiedzisuma T / tᵢprzerwij, zanim się przepełni Rozwiąż 25 k-ta liczba tabliczki mnożeniatrudne✓ zaliczone Tabliczka n × m, wszystkie iloczyny ustawione rosnąco. Jaka liczba stoi na miejscu k? Zgaduj binarnie wartość i licz iloczyny ≤ X. wyszukiwanie binarne po odpowiedzimin(m, X / i)O(n log) Rozwiąż 26 Trójkąty z patykówtrudne✓ zaliczone Ile trójek patyków tworzy trójkąt? Po posortowaniu dla każdego najdłuższego boku dwa wskaźniki — O(n²) zamiast O(n³). nierówność trójkątasortdwa wskaźniki Rozwiąż 27 Dzielniki wszystkich liczb do ntrudne✓ zaliczone Suma liczby dzielników wszystkich liczb od 1 do n, dla n do 10¹². Pary (d, w) z d · w ≤ n i sztuczka z pierwiastkiem. n / dpary d · w ≤ nO(√n) Rozwiąż 28 Wielki finał: wyprzedażtrudne✓ zaliczone Milion produktów i 3000 klientów z budżetami. Każdy kupuje jak najwięcej najtańszych. Sortowanie, sumy prefiksowe i upper_bound razem. sortsumy prefiksoweupper_bound Rozwiąż

Częste błędy i dobre praktyki

🧮
Licz, zanim napiszesz
Przed pisaniem programu wstaw największe n z treści do złożoności swojego pomysłu. Kilka minut liczenia oszczędza godzinę pisania rozwiązania, które i tak nie zdąży.
📏
Ograniczenia podpowiadają
n ≤ 20 — wszystkie podzbiory. n ≤ 5000 — pętla w pętli. n ≤ 10⁶ — sortowanie. n ≤ 10¹⁸ — wzór albo połowienie. Autor zadania dobiera ograniczenia pod konkretną złożoność.
🪵
Płot i słupki
Od a do b włącznie jest b − a + 1 liczb, a nie b − a. Gdy a > b — zero. Sprawdzaj wzór na małym przykładzie, który da się policzyć na palcach.
✖️
W środku mnożymy
Pętle jedna po drugiej — obroty się dodają (n + m). Pętla wewnątrz pętli — mnożą (n · m). Połowa kwadratu (pary i < j) to wciąż O(n²).
✂️
Logarytm jest malutki
Pętla, która dzieli dane na pół, robi najwyżej około 60 obrotów nawet dla 10¹⁸. 2¹⁰ ≈ tysiąc — zapamiętaj, a policzysz każdy logarytm w głowie.
👀
Ukryte pętle
sort, count, find, erase z początku vectora i s = s + c same są pętlami. Wywołane w pętli zamieniają O(n) w O(n²). Napisy buduj przez s += c.
🔁
Ta sama praca w kółko
Gdy program dla każdego pytania przechodzi wszystkie dane od nowa — przygotuj je raz: sumy prefiksowe, tablica zliczeń, sito, tablica różnic. O(n · q) zamienia się w O(n + q).
↔️
while w for to nie zawsze n²
W dwóch wskaźnikach i oknie każdy wskaźnik idzie tylko do przodu — razem najwyżej 2n kroków. Licz, ile razy łącznie wykona się wnętrze, a nie ile jest pętli.
💥
Duże n, duże liczby
Wzory na liczbę obrotów i sumy rosną szybko: n * (n - 1) dla n = 10⁹ to 10¹⁸. Licznik pętli do pierwiastka (d * d) i generator (x * a) — też w long long.
🧪
Wzór sprawdzaj pętlą
Nowy wzór łatwo pomylić o jeden. Napisz obok wolną pętlę z licznikiem, porównaj wyniki dla małych n, a dopiero potem wyślij wersję ze wzorem.
🎲
Generator: pierwsza liczba to s
x₁ = s, a wzór x[i] = (x[i-1] * a + b) % m stosujesz od drugiej liczby. Przed rozwiązaniem sprawdź na kartce kilka pierwszych liczb z przykładu w treści.
⏱️
TLE to nie błąd w wyniku
Time limit exceeded znaczy, że program nie zdążył — nie że liczy źle. Nie szukaj literówek: policz złożoność i znajdź pomysł o lepszym kształcie wzrostu.

Co dalej?

Od teraz przy każdym zadaniu zadawaj sobie dwa pytania: czy mój program liczy dobrze — i czy zdąży? Złożoność czasowa będzie Ci towarzyszyć przez cały trzeci etap. Następna lekcja to zbiór (set): struktura, która trzyma liczby posortowane i bez powtórzeń, a dodaje, usuwa i wyszukuje elementy w O(log n) — czyli robi „sortuj i szukaj” na bieżąco, nawet gdy dane się zmieniają. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.