C++ · Etap 2 · Lekcja 16

Wartość bezwzględna — wszystko o odległości

Ile pięter przejedzie winda z garażu na poziomie −2 na piąte piętro? Kto w zgadywance był bliżej sekretnej liczby? Ile ruchów potrzebuje król, żeby przejść przez szachownicę, i w którym miejscu ulicy powinni spotkać się przyjaciele, żeby razem przejść jak najmniej? Wszystkie te pytania dotyczą odległości, a odległość nigdy nie jest ujemna. Do jej liczenia służy jedno małe narzędzie: wartość bezwzględna, czyli „liczba bez minusa” — w C++ funkcja abs. W tej lekcji poznasz ją od samego początku: na osi liczbowej, w if-ie i jako gotową funkcję, z jej pułapkami. Potem użyjesz jej do odległości między liczbami, szukania najbliższej wartości, liczenia tras windy i kroków po kratce, do przedziałów i tarczy zamka szyfrowego, a na koniec odkryjesz, dlaczego najlepsze miejsce zbiórki to mediana. Po każdej części czekają ćwiczenia ze sprawdzarką.

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 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 i Silnia. Funkcję abs już kilka razy widziałeś: w lekcji o parach liczyłeś nią odległość taksówkarza, w lekcji o max i min — kto w zgadywance był najbliżej celu, w lekcji o sortowaniu — sortowałeś liczby według odległości od zera, a w lekcji o zaokrąglaniu porównywałeś liczby z przecinkiem przez abs(a - b) < 1e-9.

Za każdym razem abs pojawiała się tylko na chwilę, jako gotowe narzędzie. Teraz poznasz ją porządnie, od samego początku. Zobaczysz, czym jest wartość bezwzględna (to odległość od zera na osi liczbowej), jak policzyć ją samemu if-em i jak działa gotowa funkcja — także z liczbami long long i double. Poznasz trzy pułapki, na które nabiera się prawie każdy początkujący. A potem — bardzo dużo zastosowań: odległość dwóch liczb, liczba najbliżej celu, trasa windy, kroki po kratce i szachownicy, rysowanie rombu, tolerancja pomiaru, tarcza zamka szyfrowego i najlepsze miejsce zbiórki.

Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw policz w głowie albo na kartce — przy odległościach bardzo pomaga narysowanie osi liczbowej — a dopiero potem sprawdzaj odpowiedź. Po każdej części rób ćwiczenia w sprawdzarce i nie idź dalej, dopóki nie przestaną sprawiać Ci kłopotu — kolejne części budują na poprzednich.

CZĘŚĆ 01–02

Odległość od zera

Oś liczbowa, |x| i liczby przeciwne, moduł przez if, funkcja abs, typy wyniku i trzy pułapki.

CZĘŚĆ 03–05

Odległość dwóch liczb

|a − b| na osi i w życiu, najbliżej i najdalej od celu, remisy, skoki między sąsiadami i trasa windy.

CZĘŚĆ 06–07

Plansza i przedziały

Taksówkarz i król na kratce, figury szachowe, romb z gwiazdek, |x − c| ≤ r, tolerancja i tarcza zamka.

CZĘŚĆ 08

Gdzie się spotkać?

Suma odległości, dlaczego najlepsza jest mediana, a nie średnia, wyrównywanie wież i zbiórka na mapie miasta.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczbę:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane. W tej lekcji uważaj szczególnie na typ wyniku: odległość dwóch liczb z zakresu int albo suma kilku odległości potrafi nie zmieścić się w int, a program nie ostrzeże Cię ani słowem. Zanim napiszesz pierwszą linijkę, zawsze zapytaj: jak duży może być wynik?

Mapa lekcji

Jak daleko jest od zera?

Zacznijmy od budynku z windą. Parter ma numer 0. Piętra nad nim mają numery 1, 2, 3 i tak dalej, a garaże pod ziemią — numery ujemne: −1, −2, −3. Winda stoi na parterze. Ile pięter musi przejechać, żeby dojechać na trzecie piętro? Trzy. A ile, żeby zjechać do garażu na poziomie −3? Też trzy — tylko w drugą stronę.

Liczba przejechanych pięter nie ma znaku. Nie da się przejechać „minus trzech pięter”. Minus w numerze garażu mówi tylko, w którą stronę jedziemy: w dół. To, ile jedziemy, to odległość — a odległość nigdy nie jest ujemna.

−5−4−2−1012453 piętra w dół3 piętra w górę−3garaż3piętro
Garaż −3 i piętro 3 leżą po dwóch stronach parteru (zera), ale tak samo daleko: 3 piętra.

Oś liczbowa

Szyb windy to po prostu oś liczbowa postawiona pionowo. Na rysunkach będziemy ją kłaść poziomo: zero w środku, liczby dodatnie w prawo, ujemne w lewo. Im dalej w prawo, tym liczba większa — dlatego −5 jest mniejsze od −2, chociaż „piątka” wygląda na większą od „dwójki”.

Odległość liczby od zera to liczba kroków długości 1, które trzeba zrobić od zera do tej liczby. Do liczby 4 robimy 4 kroki w prawo. Do liczby −4 — 4 kroki w lewo. Obie leżą 4 kroki od zera.

−6−5−3−2−10123564 kroki4 kroki−4x4y
Wartość bezwzględna Wartość bezwzględna liczby x (mówimy też: moduł liczby x) to jej odległość od zera na osi liczbowej. Zapisujemy ją między dwiema pionowymi kreskami: |x|, a czytamy „moduł x” albo „wartość bezwzględna x”. Na przykład |4| = 4, |−4| = 4 i |0| = 0.

Moduł w praktyce: liczba bez minusa

x|x|dlaczego
77dodatnia — bez zmian
−77ujemna — bez minusa
1212dodatnia — bez zmian
−1212ujemna — bez minusa
−11ujemna — bez minusa
00zero leży w zerze
−250250ujemna — bez minusa
30003000dodatnia — bez zmian

Na co dzień moduł liczy się bardzo prosto:

• jeśli liczba jest dodatnia albo równa zero, jej moduł to ta sama liczba,
• jeśli liczba jest ujemna, jej moduł to ta liczba bez minusa.

Dlatego wartość bezwzględną nazywa się potocznie „liczbą bez minusa”. Zapamiętaj jednak, skąd się bierze: to odległość. Ten obraz przyda Ci się w każdej kolejnej części lekcji.

Pobaw się suwakiem poniżej. Przesuwaj x i patrz, jak zmienia się jego odległość od zera. Szare kółko to liczba „po drugiej stronie” zera — wrócimy do niej za chwilę.

Odległość od zera — przesuwaj suwak
Ta ramka działa po włączeniu JavaScriptu.

Minus przed liczbą: liczba przeciwna

minus.cpp
int x = -5;
cout << -x << "\n";
int y = 5;
cout << -y << "\n";
cout << -(-8) << "\n";
cout << x << " " << y << "\n";
▶ Wyjście
5 -5 8 -5 5

Zapis -x w C++ oznacza liczbę przeciwną do x: tę, która leży po drugiej stronie zera, tak samo daleko. Dla 5 to −5, a dla −5 to 5 — bo „minus minus pięć” to plus pięć.

Zwróć uwagę na ostatni wiersz: samo -x nie zmienia zmiennej x. Wypisujemy liczbę przeciwną, ale w x dalej siedzi −5. Żeby zmienić zmienną, trzeba przypisać: x = -x;.

Czy w takim razie moduł to po prostu -x? Nie! Dla liczby ujemnej tak: -(-5) to 5. Ale dla dodatniej -x robi liczbę ujemną: -(5) to −5, a moduł 5 to 5. Minus trzeba więc dopisać tylko wtedy, gdy liczba jest ujemna. A „tylko wtedy, gdy” w C++ to if.

Moduł przez if

modul_if.cpp
#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;
    if (x < 0) {
        x = -x;      // zmieniamy znak tylko liczbie ujemnej
    }
    cout << x << "\n";
    return 0;
}
▶ Wejście 1
-8
▶ Wyjście 1
8
▶ Wejście 2
3
▶ Wyjście 2
3
▶ Wejście 3
0
▶ Wyjście 3
0
wczytane xx < 0?co robi programwypisuje
−8takx = -x, czyli 88
3nienic nie zmienia3
0nienic nie zmienia0

Trzy wejścia — trzy różne drogi przez program. Liczba ujemna wchodzi do if-a i zmienia znak. Dodatnia i zero przechodzą obok, bez zmian.

Co z zerem? Warunek 0 < 0 jest fałszywy, więc zero zostaje zerem. Gdyby nawet weszło do if-a, -0 to dalej 0 — w liczbach całkowitych nie ma „minus zera”.

Liczby przeciwne mają ten sam moduł

Liczby 6 i −6 nazywamy przeciwnymi: leżą po dwóch stronach zera, w tej samej odległości. Dlatego zawsze |x| = |-x| — liczba i liczba do niej przeciwna mają ten sam moduł. Na osi wyglądają jak odbicie w lustrze, a lustrem jest zero.

Z tej symetrii wynika ważna rzecz: jeśli wiesz, że |x| = 4, to x może być równe 4 albo −4. Dwie liczby leżą 4 kroki od zera — jedna z prawej, druga z lewej. Wyjątkiem jest zero: |x| = 0 ma tylko jedno rozwiązanie, x = 0. A |x| = −2 nie ma żadnego — odległość nie może być ujemna.

−6−5−3−2−101235644−4x = −44x = 4
Równanie |x| = 4 ma dwa rozwiązania: 4 i −4. Każde leży 4 kroki od zera.
rownanie.cpp
#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;               // szukamy x, dla których |x| = k
    if (k > 0) {
        cout << -k << " " << k << "\n";
    } else if (k == 0) {
        cout << 0 << "\n";
    } else {
        cout << "BRAK\n";
    }
    return 0;
}
▶ Wejście 1
4
▶ Wyjście 1
-4 4
▶ Wejście 2
0
▶ Wyjście 2
0
▶ Wejście 3
-2
▶ Wyjście 3
BRAK

Ten program rozwiązuje równanie |x| = k i rozróżnia trzy przypadki:

• k > 0 — dwa rozwiązania, wypisane rosnąco: najpierw −k, potem k,
• k == 0 — jedno rozwiązanie: 0,
• k < 0 — brak rozwiązań, bo moduł nie bywa ujemny.

W zadaniach z wartością bezwzględną prawie zawsze trzeba osobno pomyśleć o zerze. Zero to jedyna liczba, która jest „przeciwna sama sobie”.

Ile liczb leży blisko zera?

−5−4−3−2−112345330zero
Liczby całkowite x, dla których |x| ≤ 3: od −3 do 3 — jest ich 7.

Ile jest liczb całkowitych, których moduł wynosi co najwyżej 3? To liczby, które leżą najwyżej 3 kroki od zera: −3, −2, −1, 0, 1, 2, 3. Razem 7.

Policzmy to sprytniej: 3 liczby po prawej, 3 po lewej i jeszcze samo zero. Ogólnie liczb całkowitych x z |x| ≤ k jest 2k + 1. Dla k = 10 to 21, a dla k = 1 000 000 000 — dwa miliardy i jeden. Taki wynik nie mieści się już w int!

Znak liczby

Moduł mówi, jak daleko od zera jest liczba. Brakuje jeszcze informacji, w którą stronę. Tę informację niesie znak liczby: 1 dla liczb dodatnich, −1 dla ujemnych i 0 dla zera. Każdą liczbę da się złożyć z tych dwóch kawałków: x = znak · |x|. Na przykład −7 = (−1) · 7, a 7 = 1 · 7.

znak.cpp
#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;
    int znak, modul;
    if (x > 0) {
        znak = 1;
        modul = x;
    } else if (x < 0) {
        znak = -1;
        modul = -x;
    } else {
        znak = 0;
        modul = 0;
    }
    cout << znak << " " << modul << "\n";
    cout << znak * modul << "\n";   // z powrotem x
    return 0;
}
▶ Wejście 1
-7
▶ Wyjście 1
-1 7 -7
▶ Wejście 2
15
▶ Wyjście 2
1 15 15

Program rozkłada liczbę na znak i moduł, a w drugim wierszu składa ją z powrotem: znak razy moduł daje dokładnie wczytaną liczbę.

Ten rozkład przyda się, gdy zadanie każe zrobić coś z samą „wielkością” liczby (na przykład z jej cyframi), a na koniec przywrócić znak.

Moduły wielu liczb, suma i suma modułów

saldo.cpp
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long suma = 0, obrot = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        suma += x;          // ze znakiem
        if (x < 0) x = -x;
        obrot += x;         // bez znaku
    }
    cout << suma << "\n" << obrot << "\n";
    return 0;
}
▶ Wejście
5 3 -4 0 -12 7
▶ Wyjście
-6 26

Wyobraź sobie konto w banku. Liczby dodatnie to wpłaty, ujemne — wypłaty: +3, −4, 0, −12, +7 zł.

Suma ze znakiem (saldo) to −6: na koncie jest o 6 zł mniej niż na początku. Wpłaty i wypłaty częściowo się znoszą.

Suma modułów (obrót) to 3 + 4 + 0 + 12 + 7 = 26: tyle pieniędzy w sumie przepłynęło przez konto. Tu nic się nie znosi, bo każdą kwotę liczymy bez znaku.

To dwie zupełnie różne liczby — w zadaniu zawsze sprawdź, o którą chodzi.

Cztery własności modułu 1) |x| ≥ 0 — moduł nigdy nie jest ujemny. 2) |x| = 0 tylko dla x = 0. 3) |−x| = |x| — liczby przeciwne mają ten sam moduł. 4) Dla x ≥ 0 moduł to x, a dla x < 0 moduł to −x — i dokładnie to robi if (x < 0) x = -x;.
Sprawdź się w głowie

Najpierw odpowiedz w głowie — przy każdej zmiennej zapisz sobie, ile wynosi — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int x = -6;
if (x < 0) x = -x;
cout << x;
Pokaż odpowiedź
6x jest ujemne, więc wchodzimy do if-a i zmieniamy znak: −(−6) = 6.
Co wypisze ten fragment?
int x = 9;
if (x < 0) x = -x;
cout << x;
Pokaż odpowiedź
9Warunek 9 < 0 jest fałszywy — liczba dodatnia przechodzi obok if-a bez zmian.
Co wypisze ten fragment?
int x = -3;
cout << -x << " " << x;
Pokaż odpowiedź
3 -3-x to liczba przeciwna, czyli 3, ale samo -x nie zmienia zmiennej — w x dalej jest −3.
Co wypisze ten fragment?
int x = 4;
x = -x;
x = -x;
cout << x;
Pokaż odpowiedź
4Dwa razy zmieniamy znak: 4 → −4 → 4. Liczba przeciwna do liczby przeciwnej to ta sama liczba.
Co wypisze ten fragment?
int a = -5, b = 2;
if (a < 0) a = -a;
if (b < 0) b = -b;
cout << a + b;
Pokaż odpowiedź
7Moduły to 5 i 2, a ich suma 7. Gdybyśmy dodali liczby ze znakiem, wyszłoby −3.
Co wypisze ten fragment?
int x = -7, z;
if (x > 0) z = 1;
else if (x < 0) z = -1;
else z = 0;
cout << z * 7;
Pokaż odpowiedź
-7Znak liczby −7 to −1, a jej moduł to 7. Znak razy moduł daje z powrotem −7.
Ile liczb policzy ta pętla?
int ile = 0;
for (int x = -5; x <= 5; x++) {
    int m = x;
    if (m < 0) m = -m;
    if (m <= 2) ile++;
}
cout << ile;
Pokaż odpowiedź
5Moduł co najwyżej 2 mają liczby −2, −1, 0, 1, 2 — czyli 2 · 2 + 1 = 5.
Co wypisze ten fragment?
int s = 0;
for (int x = -3; x <= 3; x++) {
    if (x < 0) s -= x;
    else s += x;
}
cout << s;
Pokaż odpowiedź
12Dla ujemnego x odejmujemy x, czyli dodajemy jego moduł. Suma modułów od −3 do 3: 3 + 2 + 1 + 0 + 1 + 2 + 3 = 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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

abs — gotowy moduł zamiast if-a

Moduł liczy się w programach tak często, że C++ ma do niego gotową funkcję: abs. Nazwa pochodzi od angielskiego absolute value — wartość bezwzględna. W nawiasie podajesz liczbę albo całe wyrażenie, a funkcja oddaje jego moduł. Robi dokładnie to samo co nasz if z części 1, tylko w jednej krótkiej linijce.

abs.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    cout << abs(-8) << "\n";
    cout << abs(3) << "\n";
    cout << abs(0) << "\n";
    cout << abs(-1000000) << "\n";
    int x = -25;
    cout << abs(x) << "\n";
    return 0;
}
▶ Wyjście
8 3 0 1000000 25

Funkcja abs mieszka w bibliotece <cmath> (jest też w <cstdlib>). Jeśli na początku programu piszesz #include <bits/stdc++.h>, jak w zadaniach ze sprawdzarką, wszystkie te biblioteki masz już dołączone.

Do abs możesz podać liczbę wpisaną wprost (abs(-8)), zmienną (abs(x)) albo dowolne wyrażenie, na przykład abs(a - b) — najpierw policzy się to, co w nawiasie, a potem moduł wyniku.

abs oddaje wynik — nie zmienia zmiennej

przypisz.cpp
int x = -5;
abs(x);              // policzone... i wyrzucone
cout << x << "\n";
x = abs(x);          // teraz zapisujemy wynik w x
cout << x << "\n";
▶ Wyjście
-5 5

To najczęstsza pomyłka przy pierwszym spotkaniu z abs. Funkcja nie zmienia zmiennej, którą jej podasz. Liczy moduł i oddaje go jako wynik — a jeśli nic z tym wynikiem nie zrobisz, po prostu przepada.

W drugiej linijce abs(x); policzyło 5 i od razu je wyrzuciło, więc w x dalej jest −5. Dopiero przypisanie x = abs(x); zapisuje wynik. Kompilator czasem ostrzega przy takiej linijce („statement has no effect” — instrukcja nic nie robi), ale nie zawsze — nie licz na to.

Jeśli nie chcesz zmieniać x, użyj wyniku od razu: cout << abs(x); albo zapisz go w nowej zmiennej: int m = abs(x);.

Cztery sposoby na moduł

zapisjak działakiedy używać
if (x < 0) x = -x;zmienia znak liczbie ujemnejgdy chcesz widzieć każdy krok — tak działa abs w środku
abs(x)gotowa funkcja, oddaje modułzawsze, gdy się da — najkrócej i najtrudniej o pomyłkę
max(x, -x)z liczby i jej przeciwnej wybiera większą — tę nieujemnąciekawostka z lekcji o max i min
x < 0 ? -x : x„skrócony if”: warunek ? wartość, gdy prawda : wartość, gdy fałszspotkasz go w cudzym kodzie — warto umieć przeczytać

Ostatni zapis to operator warunkowy ? :. Czyta się go tak: „czy x < 0? jeśli tak, to −x, a jeśli nie, to x”. Działa jak if, ale zamiast wykonywać instrukcje, wybiera jedną z dwóch wartości. Nie musisz go używać — wystarczy, że go rozpoznasz.

abs w wyrażeniach — uważaj, co jest w nawiasie

wyrazenia.cpp
int x = -4;
cout << abs(x) + 1 << "\n";
cout << 2 * abs(x) << "\n";
cout << abs(x - 3) << "\n";
cout << abs(x) - 3 << "\n";
cout << abs(-x) << "\n";
cout << -abs(x) << "\n";
cout << abs(abs(x)) << "\n";
▶ Wyjście
5 8 7 1 4 -4 4
wyrażenie (x = −4)rachunekwynik
abs(x) + 14 + 15
2 * abs(x)2 · 48
abs(x - 3)|−4 − 3| = |−7|7
abs(x) - 34 − 31
abs(-x)|4|4
-abs(x)−(4)−4
abs(abs(x))|4|4

Porównaj dwa fioletowe wyniki. abs(x - 3) najpierw odejmuje, a potem bierze moduł: |−7| = 7. abs(x) - 3 najpierw bierze moduł, a potem odejmuje: 4 − 3 = 1. Nawias ma znaczenie! Zapamiętaj też, że -abs(x) jest zawsze ujemne albo równe zero, a abs(abs(x)) to po prostu abs(x) — moduł liczby, która już jest nieujemna, niczego nie zmienia.

Suma modułów to nie moduł sumy

ab|a| + |b||a + b|
5388
−5−388
5−382
−5382
4−480

Gdy a i b mają ten sam znak, obie wersje dają to samo. Gdy mają różne znaki, liczby częściowo się znoszą i |a + b| wychodzi mniejsze.

Wyobraź sobie spacer po osi: 5 kroków w prawo, potem 3 w lewo. Przeszedłeś |5| + |−3| = 8 kroków, ale stoisz tylko |5 + (−3)| = 2 kroki od startu. Dlatego zawsze |a + b| ≤ |a| + |b| — droga na skróty nigdy nie jest dłuższa niż spacer.

abs działa dla każdego typu liczbowego

typy.cpp
cout << abs(-7) / 2 << "\n";        // int
cout << abs(-7.0) / 2 << "\n";      // double
long long duza = -3000000000LL;
cout << abs(duza) << "\n";          // long long
cout << abs(-2.75) << "\n";         // double
▶ Wyjście
3 3.5 3000000000 2.75

abs zwraca wynik tego samego typu, co liczba w nawiasie. Z int robi int, z long long — long long, a z double — double.

Dlatego abs(-7) / 2 to dzielenie całkowite: 7 / 2 = 3. A abs(-7.0) / 2 to dzielenie liczb z przecinkiem: 3.5. Reguła jest ta sama co zawsze — typ wyniku decyduje, jak liczy się dalej.

W starszych programach (i w języku C) spotkasz jeszcze nazwy fabs (dla double) i llabs (dla long long). W C++ wystarczy jedna nazwa: abs.

Pułapka 1: najmniejsza liczba int

int_min.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int x;
    cin >> x;
    cout << abs(x) << "\n";       // nie mieści się w int!
    long long y = x;
    cout << abs(y) << "\n";       // w long long jest dobrze
    return 0;
}
▶ Wejście
-2147483648
▶ Wyjście
-2147483648 2147483648

Typ int mieści liczby od −2 147 483 648 do 2 147 483 647. Zauważ, że liczb ujemnych jest o jedną więcej niż dodatnich. Najmniejsza liczba int nie ma więc pary: jej moduł, 2 147 483 648, jest o 1 za duży dla int.

Co wtedy robi abs? W C++ to „zachowanie niezdefiniowane” — program może zrobić cokolwiek. Na prawie każdym komputerze wychodzi z powrotem ta sama ujemna liczba, jak w pierwszym wierszu. Moduł ujemny — coś, co według matematyki jest niemożliwe!

Ratunek: gdy dane mogą mieć pełny zakres int, wczytuj je do long long. W long long moduł −2 147 483 648 mieści się bez trudu.

Pułapka 2: reszta z liczby ujemnej

cyfry.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long x;
    cin >> x;
    cout << x % 10 << " " << abs(x % 10) << "\n";
    x = abs(x);                 // od teraz liczba bez minusa
    int cyfry = 0, suma = 0;
    if (x == 0) cyfry = 1;
    while (x > 0) {
        suma += x % 10;
        cyfry++;
        x /= 10;
    }
    cout << cyfry << " " << suma << "\n";
    return 0;
}
▶ Wejście
-4071
▶ Wyjście
-1 1 4 12

Z lekcji o if i o modulo pamiętasz, że w C++ reszta ma znak liczby dzielonej: -4071 % 10 to −1, a nie 1. Ostatnią cyfrę liczby ujemnej bierzemy więc jako abs(x % 10).

Jeszcze gorzej z pętlą rozbierającą liczbę na cyfry. Warunek while (x > 0) dla liczby ujemnej jest fałszywy od razu, więc pętla nie wykona się ani razu i program powie, że −4071 ma 0 cyfr. Rozwiązanie: przed pętlą zrób x = abs(x); — cyfry liczby i jej modułu są przecież te same.

Zero trzeba obsłużyć osobno: ma jedną cyfrę, choć pętla też się dla niego nie wykona.

Pułapka 3 czeka w części 3 Trzecia pułapka dotyczy odległości dwóch liczb: różnica dwóch dużych liczb int potrafi nie zmieścić się w int, a długości napisów (size()) w ogóle nie mają minusa. Zobaczysz ją, gdy zaczniemy odejmować.
Sprawdź się w głowie

Najpierw policz w głowie — uważaj na nawiasy i na typy — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << abs(-12) + abs(5);
Pokaż odpowiedź
1712 + 5 = 17. Każdy moduł liczymy osobno, a potem dodajemy.
Co wypisze ten fragment?
cout << abs(-12 + 5);
Pokaż odpowiedź
7Najpierw nawias: −12 + 5 = −7, a potem moduł: 7. To nie to samo co abs(-12) + abs(5).
Co wypisze ten fragment?
int x = -3;
abs(x);
cout << x;
Pokaż odpowiedź
-3Wynik abs(x) nigdzie nie został zapisany, więc x się nie zmieniło. Trzeba napisać x = abs(x);.
Co wypisze ten fragment?
cout << abs(-9) / 2 << " " << abs(-9.0) / 2;
Pokaż odpowiedź
4 4.5abs z int daje int, więc 9 / 2 = 4 (dzielenie całkowite). abs z double daje double: 9.0 / 2 = 4.5.
Co wypisze ten fragment?
int x = -4;
cout << abs(x - 3) << " " << abs(x) - 3;
Pokaż odpowiedź
7 1|−4 − 3| = |−7| = 7, a |−4| − 3 = 4 − 3 = 1. Nawias decyduje, co najpierw.
Co wypisze ten fragment?
cout << -abs(-6) << " " << abs(-(-6));
Pokaż odpowiedź
-6 6-abs(-6) to minus moduł, czyli −6. -(-6) to 6, a jego moduł to 6.
Co wypisze ten fragment?
int x = -1234;
cout << x % 10 << " " << abs(x % 10);
Pokaż odpowiedź
-4 4Reszta ma znak liczby dzielonej, więc −1234 % 10 = −4. Moduł daje ostatnią cyfrę: 4.
Co wypisze ten fragment?
int x = -7;
cout << max(x, -x) << " " << min(x, -x);
Pokaż odpowiedź
7 -7Z liczby i jej przeciwnej max wybiera nieujemną (to |x|), a min — niedodatnią (to −|x|).
Ć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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Jak daleko jest z a do b?

Do tej pory mierzyliśmy odległość od zera. Teraz zmierzymy odległość między dowolnymi dwiema liczbami. Znowu liczymy kroki na osi. Z 2 do 7 jest 5 kroków. Z −3 do 4 — 7 kroków (3 kroki do zera i jeszcze 4 dalej). Z −6 do −2 — 4 kroki.

−7−6−5−4−3−2−10123456785 kroków7 kroków4 kroki
Trzy odległości na jednej osi: z 2 do 7, z −3 do 4 i z −6 do −2.

Jak to policzyć bez rysowania? Od większej liczby odejmij mniejszą: 7 − 2 = 5, 4 − (−3) = 7, −2 − (−6) = 4. Zgadza się z rysunkiem.

Kłopot w tym, że program zwykle nie wie, która liczba jest większa. Co się stanie, gdy odejmiemy w złej kolejności? 2 − 7 = −5. Wyszła ta sama piątka, tylko z minusem! Minus mówi jedynie, że idziemy w lewo zamiast w prawo. A jak pozbyć się minusa — już wiesz: wziąć moduł. Stąd najważniejszy wzór tej lekcji:

odległość liczb a i b = |a − b| = |b − a|
aba − bb − a|a − b|
27−555
725−55
−34−777
−6−2−444
55000

Popatrz na kolumny a − b i b − a: w każdym wierszu to ta sama liczba z przeciwnym znakiem. Liczby przeciwne mają ten sam moduł (pamiętasz z części 1?), więc |a − b| i |b − a| są zawsze równe. Kolejność odejmowania nie ma znaczenia.

Ostatni wiersz: odległość jest równa 0 wtedy i tylko wtedy, gdy liczby są równe.

A zero? To po prostu szczególny przypadek: odległość x od zera to |x − 0| = |x|.

Sprawdź to na suwakach. Ustaw a i b w różnych miejscach — także oba ujemne i oba po różnych stronach zera — i porównaj cztery kafelki.

Odległość dwóch liczb — przesuwaj a i b
Ta ramka działa po włączeniu JavaScriptu.
Odległość dwóch liczb Odległość liczb a i b na osi to abs(a - b). Kolejność nie ma znaczenia: abs(a - b) == abs(b - a). Ten sam wynik da max(a, b) - min(a, b) z lekcji o max i min — większa minus mniejsza. Odległość wynosi 0 tylko dla równych liczb.

O ile się różnią?

roznica.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << abs(a - b) << "\n";
    return 0;
}
▶ Wejście 1
3 10
▶ Wyjście 1
7
▶ Wejście 2
10 3
▶ Wyjście 2
7
▶ Wejście 3
-4 6
▶ Wyjście 3
10

Cały program to jedna linijka z abs. Bez niej trzeba by napisać if, który sprawdza, która liczba jest większa, i odejmuje w dobrej kolejności. Z abs odejmujesz „jak leci”, a moduł naprawia znak.

W zadaniach to pytanie przychodzi w wielu przebraniach: o ile się różnią?, jak daleko są od siebie?, ile lat różnicy?, o ile zmieniła się temperatura? — za każdym razem odpowiedzią jest abs(a - b).

Odległość w życiu

sytuacjaab|a − b|
różnica wieku: Ala urodzona w 2012, Bartek w 2009201220093 lata
temperatura: rano −4°C, w południe 5°C−459 stopni
winda: z garażu −2 na piętro 5−257 pięter
wysokość: Rysy 2499 m, brzeg Morza Martwego około −430 m2499−4302929 m
historia: Grunwald 1410, odsiecz wiedeńska 168314101683273 lata
pozycje w tablicy: element 3 i element 113118 miejsc

Zwróć uwagę na temperaturę i windę. Gdy jedna liczba jest ujemna, a druga dodatnia, odległość jest sumą ich modułów: od −4 do 0 są 4 stopnie, a od 0 do 5 — jeszcze 5. Wzór abs(a - b) pilnuje tego sam: 5 − (−4) = 5 + 4 = 9.

Kilka odcinków po kolei: winda wezwana na inne piętro

winda.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int p, q, r;    // winda stoi na p, wzywają ją z q, jedzie na r
    cin >> p >> q >> r;
    int dojazd = abs(p - q);
    int kurs = abs(q - r);
    cout << dojazd << " + " << kurs << " = " << dojazd + kurs << "\n";
    return 0;
}
▶ Wejście
3 -1 6
▶ Wyjście
4 + 7 = 11
−20124574 (dojazd)7 (kurs)3p−1q6r

Winda stoi na piętrze 3. Ktoś wzywa ją z garażu −1 i jedzie na piętro 6. Najpierw winda zjeżdża po pasażera: |3 − (−1)| = 4 piętra. Potem wiezie go na górę: |−1 − 6| = 7 pięter. Razem 11.

Gdy trasa ma kilka odcinków, liczymy odległość każdego odcinka osobno i dodajemy. W części 5 zrobimy tak samo z całą listą przystanków.

Czas, litery i inne „osie”

czas.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int h1, m1, h2, m2;
    cin >> h1 >> m1 >> h2 >> m2;
    int t1 = h1 * 60 + m1;      // minuty od północy
    int t2 = h2 * 60 + m2;
    cout << abs(t1 - t2) << "\n";
    return 0;
}
▶ Wejście
9 10 7 45
▶ Wyjście
85
litery.cpp
char a = 'c', b = 'k';
cout << abs(a - b) << "\n";
cout << abs('z' - 'a') << "\n";
▶ Wyjście
8 25

Oś liczbowa nie musi składać się z „liczb z zadania”. Godziny zamieniamy na minuty od północy i dopiero wtedy odejmujemy: 9:10 to 550 minut, 7:45 to 465 minut, różnica 85.

Litery w C++ też są liczbami (pamiętasz kody znaków z lekcji o napisach?), a kolejne litery alfabetu mają kolejne kody. Dlatego abs(a - b) dla dwóch liter to ich odległość w alfabecie: od c do k jest 8 kroków.

Czy c leży pomiędzy a i b?

Ciekawe zastosowanie odległości: sprawdzenie, czy liczba c leży między a i b (gdy nie wiemy, która z liczb a, b jest mniejsza). Jeśli c leży pomiędzy, to droga z a do c i dalej z c do b ma dokładnie tę samą długość co droga prosto z a do b. Jeśli c leży poza — trzeba „nadłożyć drogi” i suma wychodzi większa.

0134679103362a5c8b
c = 5 leży pomiędzy: 3 + 3 = 6 = |a − b|.
0134578107342a9c6b
c = 9 leży poza: 7 + 3 = 10, a |a − b| = 4.
pomiedzy.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (abs(a - c) + abs(c - b) == abs(a - b)) {
        cout << "TAK\n";
    } else {
        cout << "NIE\n";
    }
    return 0;
}
▶ Wejście 1
8 2 5
▶ Wyjście 1
TAK
▶ Wejście 2
2 6 9
▶ Wyjście 2
NIE
▶ Wejście 3
2 6 6
▶ Wyjście 3
TAK

Program działa bez względu na to, czy a jest mniejsze, czy większe od b — w pierwszym wejściu a = 8, b = 2. Trzecie wejście pokazuje, że koniec odcinka (c = b) też liczy się jako „pomiędzy”.

Ten sam test da się zapisać przez max i min: min(a, b) <= c && c <= max(a, b). Obie wersje są dobre — wybierz tę, która jest dla Ciebie czytelniejsza.

Pułapka 3: różnica też ma swój zakres

zakres_zle.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << abs(a - b) << "\n";
    return 0;
}
▶ Wejście
2000000000 -2000000000
▶ Wyjście
294967296
zakres_dobrze.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    cout << abs(a - b) << "\n";
    return 0;
}
▶ Wejście
2000000000 -2000000000
▶ Wyjście
4000000000

Obie liczby mieszczą się w int (do 2 147 483 647), ale ich odległość — 4 000 000 000 — już nie. Odejmowanie a - b przepełnia się, zanim abs w ogóle zacznie działać, i z czterech miliardów robi się bzdura. W long long wszystko jest w porządku.

Zasada: odległość dwóch liczb może być dwa razy większa niż same liczby, a suma kilku odległości — jeszcze większa. Gdy w zadaniu liczby sięgają miliarda, a Ty dodajesz kilka odległości, użyj long long.

Długości napisów nie mają minusa

dlugosci.cpp
string s = "kot", t = "hipopotam";
cout << abs(s.size() - t.size()) << "\n";
▶ Kompilator
error: call of overloaded 'abs(...size_type)' is ambiguous
dlugosci_bez_abs.cpp
string s = "kot", t = "hipopotam";
cout << s.size() - t.size() << "\n";
▶ Wyjście
18446744073709551610
dlugosci_dobrze.cpp
string s = "kot", t = "hipopotam";
cout << abs((int)s.size() - (int)t.size()) << "\n";
▶ Wyjście
6

size() zwraca liczbę bez znaku — długość nie bywa ujemna, więc C++ trzyma ją w specjalnym typie, który nie zna minusa. Odejmowanie 3 − 9 w takim typie nie daje −6, tylko „przekręca się” na ogromną liczbę, jak licznik kilometrów cofnięty poniżej zera.

Do tego abs nie wie, co zrobić z liczbą bez znaku, i kompilator odmawia (komunikat „ambiguous” znaczy „niejednoznaczne”). Ratunek: zamień obie długości na int przed odejmowaniem.

Sprawdź się w głowie

Najpierw policz w głowie — przy ujemnych liczbach narysuj sobie oś — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << abs(3 - 10) << " " << abs(10 - 3);
Pokaż odpowiedź
7 7Kolejność odejmowania nie ma znaczenia: |−7| = |7| = 7.
Co wypisze ten fragment?
int a = -4, b = 6;
cout << abs(a - b);
Pokaż odpowiedź
10−4 − 6 = −10, moduł 10. Na osi: 4 kroki do zera i jeszcze 6 dalej.
Co wypisze ten fragment?
int a = -4, b = -9;
cout << abs(a - b);
Pokaż odpowiedź
5−4 − (−9) = −4 + 9 = 5. Obie liczby leżą po tej samej stronie zera, więc ich moduły się odejmują: 9 − 4 = 5.
Ile pięter przejedzie winda?
int p = 2, q = -3, r = 4;
cout << abs(p - q) + abs(q - r);
Pokaż odpowiedź
12Dojazd z 2 do −3: 5 pięter. Kurs z −3 do 4: 7 pięter. Razem 12.
Co wypisze ten fragment?
cout << abs('z' - 'a');
Pokaż odpowiedź
25Litery mają kolejne kody, więc od a do z jest 25 kroków (liter jest 26, ale kroków między pierwszą a ostatnią — 25).
Co wypisze ten fragment?
int a = 5, b = 1, c = 3;
cout << (abs(a - c) + abs(c - b) == abs(a - b));
Pokaż odpowiedź
12 + 2 = 4 = |5 − 1|, więc c leży pomiędzy a i b — porównanie jest prawdziwe i wypisuje się 1.
Co wypisze ten fragment?
int a = 5, b = 1, c = 7;
cout << abs(a - c) + abs(c - b) - abs(a - b);
Pokaż odpowiedź
42 + 6 − 4 = 4. Gdy c leży poza odcinkiem, „nadkładamy drogi” — tu dwa razy po 2 kroki za punkt 5.
Ile minut minęło?
int t1 = 8 * 60 + 50, t2 = 10 * 60 + 5;
cout << abs(t1 - t2);
Pokaż odpowiedź
758:50 to 530 minut od północy, 10:05 to 605. Różnica: 75 minut, czyli godzina i kwadrans.
Ć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 O ile się różnią?łatwe✓ zaliczone Odległość |a − b| dla wielu par. Liczby sięgają dwóch miliardów — różnica nie zmieści się w int. abs(a - b)long longkolejność bez znaczenia Rozwiąż 3.2 Winda na wezwaniełatwe✓ zaliczone Winda dojeżdża z poziomu p po pasażera na poziom q i wiezie go na r. Ile pięter? |p − q| + |q − r|piętra ujemnekilka odcinków Rozwiąż 3.3 Ile minut różnicy?łatwe✓ zaliczone Dwie godziny z jednego dnia — ile minut je dzieli? Zamień je na minuty od północy. minuty od północyabs(t1 - t2)kolejność bez znaczenia Rozwiąż 3.4 Litery w alfabeciełatwe✓ zaliczone Odległość dwóch liter w alfabecie i ile liter stoi ściśle pomiędzy nimi. abs(a - b) dla charkody literściśle pomiędzy Rozwiąż 3.5 Kto był bliżej?łatwe✓ zaliczone Zgadywanka dla dwojga: sekret s, strzał Ali i strzał Bartka. Kto wygrał — a może remis? abs(x - s)porównanie odległościremis Rozwiąż 3.6 Czy leży pomiędzy?średnie✓ zaliczone Czy c leży między a i b (końce się liczą)? Nie wiadomo, która z liczb a, b jest mniejsza. |a − c| + |c − b| = |a − b|min i maxlong long Rozwiąż 3.7 Wyrównaj długościłatwe✓ zaliczone Ile liter dopisać do krótszego słowa? Uwaga: size() nie ma minusa. (int)s.size()absliczby bez znaku Rozwiąż 3.8 Największa zmiana temperaturyśrednie✓ zaliczone Temperatura rano i wieczorem przez n dni. Który dzień miał największą zmianę? abs(w - r)rekordremis: najwcześniejszy Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Kto jest najbliżej? Rekord według odległości

W lekcji o max i min poznałeś wzorzec rekordu: pierwszą liczbę uznajemy za najlepszą, a potem każdą kolejną porównujemy z dotychczasową najlepszą i podmieniamy, gdy nowa jest lepsza. Do tej pory „lepsza” znaczyło „większa” albo „mniejsza”. Teraz „lepsza” będzie znaczyło bliższa — czyli o mniejszej odległości.

Zacznijmy od najprostszego celu: zera. Która z liczb −7, 3, −2, 9, 5 leży najbliżej zera? Odległości od zera to moduły: 7, 3, 2, 9, 5. Najmniejsza jest odległość 2 — ma ją liczba −2. Odpowiedzią jest −2, a nie 2: pytamy o liczbę, nie o odległość.

−8−6−5−4−3−10124678102 — najbliżej3−73−295
Liczba −2 leży 2 kroki od zera — bliżej niż każda inna.

Porównuj odległości, zapamiętuj liczbę

najblizej_zle.cpp
int t[5] = {-7, 3, -2, 9, 5};
int najlepsza = abs(t[0]);
for (int i = 1; i < 5; i++) {
    if (abs(t[i]) < najlepsza) {
        najlepsza = abs(t[i]);   // zgubiliśmy znak!
    }
}
cout << najlepsza << "\n";
▶ Wyjście
2
najblizej_dobrze.cpp
int t[5] = {-7, 3, -2, 9, 5};
int najlepsza = t[0];
for (int i = 1; i < 5; i++) {
    if (abs(t[i]) < abs(najlepsza)) {
        najlepsza = t[i];        // zapamiętujemy oryginał
    }
}
cout << najlepsza << "\n";
▶ Wyjście
-2

Lewy program zapisuje do zmiennej odległość, a potem nie ma już skąd wziąć znaku — wypisuje 2. Prawy zapisuje samą liczbę, a odległość liczy dopiero przy porównaniu: abs(t[i]) < abs(najlepsza). To najważniejsza zasada tej części: porównuj odległości, a zapamiętuj liczby.

Najbliżej dowolnego celu

Najbliżej zera to szczególny przypadek. W zgadywance celem jest sekretna liczba c, a odległość liczby x od celu to — z części 3 — abs(x - c). Wzorzec zostaje ten sam, zmienia się tylko miara. Prześledź go krok po kroku w ramce poniżej. Zwróć uwagę, co się dzieje przy remisie.

Najbliżej celu — krok po kroku
Ta ramka działa po włączeniu JavaScriptu.
zgadywanka.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int c, n;
    cin >> c >> n;
    int najlepsza;
    cin >> najlepsza;                  // pierwsza liczba
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        if (abs(x - c) < abs(najlepsza - c)) {
            najlepsza = x;
        }
    }
    cout << najlepsza << "\n";
    return 0;
}
▶ Wejście
10 6 12 5 9 20 11 15
▶ Wyjście
9
x|x − 10|najlepsza po kroku
12212 (pierwsza)
5512 — 5 > 2
919 — 1 < 2
20109
1119 — remis, zostaje
1559

Liczby 9 i 11 leżą tak samo blisko celu 10 — obie o 1. Warunek < jest przy remisie fałszywy, więc zostaje ta, która przyszła wcześniej: 9.

Remisy: kto wygrywa?

Remis przy odległościach zdarza się bardzo często: każda liczba ma „bliźniaka” po drugiej stronie celu (9 i 11 przy celu 10, −3 i 3 przy zerze). Dlatego zadania prawie zawsze mówią, co zrobić przy remisie. Trzy najczęstsze reguły i ich warunki:

reguła z zadaniawarunek podmiany
przy remisie wygrywa wcześniejszaabs(x - c) < abs(naj - c)
przy remisie wygrywa późniejszaabs(x - c) <= abs(naj - c)
przy remisie wygrywa mniejsza liczbad < najD || (d == najD && x < naj)
przy remisie wygrywa większa liczbad < najD || (d == najD && x > naj)
remis_mniejsza.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int c, n;
    cin >> c >> n;
    int naj, najD;
    cin >> naj;
    najD = abs(naj - c);
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        int d = abs(x - c);
        if (d < najD || (d == najD && x < naj)) {
            naj = x;
            najD = d;
        }
    }
    cout << naj << " " << najD << "\n";
    return 0;
}
▶ Wejście
10 4 12 15 8 30
▶ Wyjście
8 2

W tej wersji odległość najlepszej liczby trzymamy w osobnej zmiennej najD, a odległość bieżącej — w d. Program jest dłuższy, ale za to warunki czyta się łatwiej i nie liczymy tego samego modułu w kółko.

12 i 8 są tak samo blisko celu 10 (odległość 2). Reguła „przy remisie mniejsza” wybiera 8, choć 12 przyszła wcześniej. Pamiętaj, żeby przy podmianie zmienić obie zmienne: naj i najD.

Pozycja, najdalej i „w zasięgu”

pozycja.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int c, n;
    cin >> c >> n;
    int t[100];
    for (int i = 0; i < n; i++) cin >> t[i];
    int blisko = 0, daleko = 0, wZasiegu = 0;
    for (int i = 0; i < n; i++) {
        if (abs(t[i] - c) < abs(t[blisko] - c)) blisko = i;
        if (abs(t[i] - c) > abs(t[daleko] - c)) daleko = i;
        if (abs(t[i] - c) <= 3) wZasiegu++;
    }
    cout << "najblizej: nr " << blisko + 1 << "\n";
    cout << "najdalej: nr " << daleko + 1 << "\n";
    cout << "w zasiegu 3: " << wZasiegu << "\n";
    return 0;
}
▶ Wejście
10 6 12 5 9 20 11 15
▶ Wyjście
najblizej: nr 3 najdalej: nr 4 w zasiegu 3: 3

Trzy pytania w jednej pętli:

• Pozycja najbliższej: zamiast liczby zapamiętujemy jej indeks. Liczby są numerowane od 1, więc wypisujemy blisko + 1.

• Najdalej: ten sam wzorzec, tylko znak > zamiast <. Najdalej od 10 jest 20 (odległość 10).

• W zasięgu: ile liczb leży co najwyżej 3 od celu? To zwykłe liczenie z warunkiem abs(x - c) <= 3: pasują 12, 9 i 11. W części 7 zobaczysz, że taki warunek opisuje cały przedział liczb.

Sąsiedzi celu z lewej i z prawej

3467811131416171259z lewej10c12z prawej15

Czasem zadanie pyta osobno o najbliższą liczbę z lewej strony celu (największą wśród liczb ≤ c) i z prawej (najmniejszą wśród liczb ≥ c). To zwykłe max i min z warunkiem — bez modułów.

Ciekawostka: najbliższa liczba w ogóle to zawsze jeden z tych dwóch sąsiadów. Liczba leżąca dalej na lewo niż sąsiad z lewej jest od celu dalej niż on — i tak samo z prawej. Wystarczy więc porównać dwóch kandydatów.

Para o sumie najbliżej zera

para.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int t[1000];
    for (int i = 0; i < n; i++) cin >> t[i];
    int najlepsza = abs(t[0] + t[1]);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            najlepsza = min(najlepsza, abs(t[i] + t[j]));
        }
    }
    cout << najlepsza << "\n";
    return 0;
}
▶ Wejście
5 -8 3 5 -2 9
▶ Wyjście
1

Miarą może być odległość od zera nie pojedynczej liczby, ale wyniku działania. Tu szukamy dwóch różnych liczb, których suma leży najbliżej zera — na przykład dwóch odważników, które jak najlepiej się równoważą.

Sprawdzamy każdą parę (i, j) z i < j — dwie pętle, jak w lekcji o tablicach. Dla każdej pary liczymy abs(t[i] + t[j]) i zapamiętujemy najmniejszą wartość przez min. Najlepsze są tu dwie pary: −8 + 9 = 1 i 3 + (−2) = 1.

Uwaga na start: najlepsza zaczyna od pierwszej prawdziwej pary (t[0], t[1]), a nie od zera — zero byłoby „lepsze” od każdej pary i nic by go nie podmieniło.

Sprawdź się w głowie

Najpierw policz w głowie — wypisz sobie odległości wszystkich liczb od celu — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t[3] = {4, -3, 8};
int naj = t[0];
for (int i = 1; i < 3; i++)
    if (abs(t[i]) < abs(naj)) naj = t[i];
cout << naj;
Pokaż odpowiedź
-3Odległości od zera: 4, 3, 8. Najmniejsza jest 3 — wypisujemy liczbę −3, ze znakiem.
Co wypisze ten fragment (z błędem)?
int t[3] = {4, -3, 8};
int naj = abs(t[0]);
for (int i = 1; i < 3; i++)
    if (abs(t[i]) < naj) naj = abs(t[i]);
cout << naj;
Pokaż odpowiedź
3Program zapamiętuje odległość zamiast liczby i gubi minus. Gdy zadanie pyta o liczbę, to błąd.
Co wypisze ten fragment?
int c = 10, t[2] = {8, 12};
int naj = t[0];
if (abs(t[1] - c) < abs(naj - c)) naj = t[1];
cout << naj;
Pokaż odpowiedź
8Remis: obie liczby są 2 od celu. Przy warunku < zostaje wcześniejsza, czyli 8.
A teraz z <= — co wypisze ten fragment?
int c = 10, t[2] = {8, 12};
int naj = t[0];
if (abs(t[1] - c) <= abs(naj - c)) naj = t[1];
cout << naj;
Pokaż odpowiedź
12Przy remisie warunek <= jest prawdziwy, więc późniejsza liczba 12 podmienia 8.
Co wypisze ten fragment?
int c = 10, t[4] = {12, 5, 9, 20};
int naj = t[0];
for (int i = 1; i < 4; i++)
    if (abs(t[i] - c) > abs(naj - c)) naj = t[i];
cout << naj;
Pokaż odpowiedź
20Szukamy najdalej (znak >). Odległości od 10: 2, 5, 1, 10 — najdalej jest 20.
Ile liczb policzy ten fragment?
int c = 10, t[5] = {8, 9, 13, 12, 7};
int ile = 0;
for (int i = 0; i < 5; i++)
    if (abs(t[i] - c) <= 2) ile++;
cout << ile;
Pokaż odpowiedź
3Odległości: 2, 1, 3, 2, 3. Co najwyżej 2 mają 8, 9 i 12.
Co wypisze ten fragment?
int t[4] = {5, -4, 4, 6};
int k = 0;
for (int i = 1; i < 4; i++)
    if (abs(t[i]) < abs(t[k])) k = i;
cout << k;
Pokaż odpowiedź
1Najbliżej zera są −4 i 4 (remis). Warunek < zostawia wcześniejszą: indeks 1.
Co wypisze ten fragment?
int t[3] = {-5, 2, 4};
int naj = abs(t[0] + t[1]);
for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 3; j++)
        naj = min(naj, abs(t[i] + t[j]));
cout << naj;
Pokaż odpowiedź
1Sumy par: −5 + 2 = −3, −5 + 4 = −1, 2 + 4 = 6. Najbliżej zera jest −1, czyli odległość 1.
Ć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 Najbliżej zerałatwe✓ zaliczone Która liczba leży najbliżej zera? Przy remisie (−3 i 3) wygrywa dodatnia. rekordabs(x) < abs(naj)remis: dodatnia Rozwiąż 4.2 Który numer jest najbliżej?łatwe✓ zaliczone Numer uczestnika najbliższego sekretnej liczbie c (przy remisie najmniejszy) i jego odległość. abs(x - c)indeks rekorduremis: pierwszy Rozwiąż 4.3 Najdalej od celułatwe✓ zaliczone Która liczba leży najdalej od c? Przy remisie wybierz większą. abs(x - c)rekord z >remis: większa Rozwiąż 4.4 W zasięgu nadajnikałatwe✓ zaliczone Ile domów leży co najwyżej d od nadajnika w punkcie c, a ile poza zasięgiem? abs(x - c) <= dliczeniekoniec się liczy Rozwiąż 4.5 Zgadywanka z imionamiśrednie✓ zaliczone Kto zgadł najbliżej sekretu? Wypisz imię — przy remisie wygrywa ten, kto zgadywał wcześniej. abs(x - s)string w rekordzieremis: wcześniejszy Rozwiąż 4.6 Najbliższy przystanekśrednie✓ zaliczone Dla każdej osoby: numer najbliższego przystanku przy drodze i odległość do niego. dwie pętlerekord dla każdego pytaniaremis: mniejszy numer Rozwiąż 4.7 Sąsiedzi celuśrednie✓ zaliczone Najbliższa liczba z lewej strony celu, najbliższa z prawej i najbliższa w ogóle. max z warunkiemmin z warunkiemBRAK Rozwiąż 4.8 Para o sumie najbliżej zeraśrednie✓ zaliczone Wybierz dwie liczby z różnych pozycji, których suma leży najbliżej zera. Sprawdź wszystkie pary. dwie pętleabs(t[i] + t[j])pary i < j Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Skoki między sąsiadami — winda, szlak i najmniejsza różnica

W wielu zadaniach dostajesz nie dwie liczby, ale cały ciąg: kolejne przystanki windy, wysokości na szlaku w górach, temperatury dzień po dniu, pozycje, które odwiedza kurier. Program przechodzi od jednej liczby do następnej, a my pytamy o skoki: jak daleko jest z każdej liczby do kolejnej?

Skok z liczby a[i - 1] do jej następczyni a[i] to — jak w części 3 — abs(a[i] - a[i - 1]). Takie dwie liczby stojące obok siebie nazywamy sąsiadami. Pętla po sąsiadach zaczyna się od i = 1, bo element o indeksie 0 nie ma poprzednika.

Przystanki windy: parter, piętro 5, piętro 2, garaż −1, piętro 7. Skoki: |5 − 0| = 5, |2 − 5| = 3, |−1 − 2| = 3, |7 − (−1)| = 8. Razem 19 pięter.

Winda zaczyna na parterze i zatrzymuje się kolejno na piętrach 5, 2, −1 i 7. Ile pięter przejechała? Sprawdź w ramce — klikaj „Krok” i patrz, jak rośnie suma.

Winda — ile pięter przejechała?
Ta ramka działa po włączeniu JavaScriptu.

Suma skoków w programie

winda_tablica.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int p[1000];
    for (int i = 0; i < n; i++) cin >> p[i];
    long long suma = 0;
    for (int i = 1; i < n; i++) {
        suma += abs(p[i] - p[i - 1]);
    }
    cout << suma << "\n";
    return 0;
}
▶ Wejście
5 0 5 2 -1 7
▶ Wyjście
19
winda_bez_tablicy.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, poprzednia;
    cin >> n >> poprzednia;
    long long suma = 0;
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        suma += abs(x - poprzednia);
        poprzednia = x;       // teraz x jest „poprzednią”
    }
    cout << suma << "\n";
    return 0;
}
▶ Wejście
5 0 5 2 -1 7
▶ Wyjście
19

Dwie wersje tego samego. Lewa wczytuje wszystko do tablicy i potem idzie po sąsiadach. Prawa w ogóle nie potrzebuje tablicy: trzyma tylko poprzednią liczbę i po każdym skoku przesuwa ją na bieżącą. To bardzo przydatny trik, gdy liczb jest dużo, a każdą potrzebujesz tylko raz.

Zauważ long long przy sumie: pojedynczy skok mieści się w int, ale tysiąc skoków po miliardzie — już nie.

ipoprzedniaxskok |x − poprzednia|suma po kroku
10555
25238
32−1311
4−17819

Największy skok

najwiekszy_skok.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int h[1000];
    for (int i = 0; i < n; i++) cin >> h[i];
    int naj = 1;                       // skok z h[0] do h[1]
    for (int i = 2; i < n; i++) {
        if (abs(h[i] - h[i - 1]) > abs(h[naj] - h[naj - 1])) {
            naj = i;
        }
    }
    cout << abs(h[naj] - h[naj - 1]) << " " << naj << "\n";
    return 0;
}
▶ Wejście
6 120 150 90 95 160 140
▶ Wyjście
65 4

To połączenie skoków z wzorcem rekordu z części 4. Każdy skok rozpoznajemy po indeksie i elementu, do którego skaczemy. Pierwszy skok ma indeks 1 (z h[0] do h[1]) i od niego zaczynamy.

Skoki: 30, 60, 5, 65, 20. Największy, 65, prowadzi z 95 do 160 — do elementu o indeksie 4.

Uwaga: skok w dół (z 150 do 90) liczy się tak samo jak w górę. Gdyby zadanie pytało tylko o największy wzrost, porównywalibyśmy różnice h[i] - h[i - 1] bez modułu.

Podejścia, zejścia i moduł

szlak.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int h[1000];
    for (int i = 0; i < n; i++) cin >> h[i];
    long long gora = 0, dol = 0, razem = 0;
    for (int i = 1; i < n; i++) {
        int d = h[i] - h[i - 1];       // ze znakiem!
        if (d > 0) gora += d;
        else dol += -d;
        razem += abs(d);
    }
    cout << gora << " " << dol << " " << razem << "\n";
    return 0;
}
▶ Wejście
5 300 450 400 600 550
▶ Wyjście
350 100 450

Szlak w górach: wysokości 300, 450, 400, 600, 550 metrów. Turystę interesują osobno podejścia i zejścia. Różnica d = h[i] - h[i - 1] ze znakiem mówi, w którą stronę idziemy: dodatnia — pod górę, ujemna — w dół.

Podejścia: 150 + 200 = 350 m. Zejścia: 50 + 50 = 100 m. A suma modułów wszystkich zmian to 450 — dokładnie podejścia plus zejścia. Moduł „skleja” obie strony w jedną liczbę.

Jeszcze jedno: koniec minus start (550 − 300 = 250) to podejścia minus zejścia (350 − 100). Różnica ze znakiem mówi, gdzie skończyliśmy; suma modułów — ile się nachodziliśmy.

Pisanie jednym palcem

palec.cpp
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() {
    string s;
    cin >> s;
    char palec = 'a';            // palec startuje na literze a
    int ruchy = 0;
    for (char z : s) {
        ruchy += abs(z - palec);
        palec = z;
    }
    cout << ruchy << "\n";
    return 0;
}
▶ Wejście
kot
▶ Wyjście
19

Klawiatura ma wszystkie litery w jednym rzędzie, od a do z. Palec stoi na literze a i przesuwa się o jedno pole na każdą literę odległości. Ile przesunięć potrzeba, żeby napisać słowo?

To ten sam wzorzec „poprzednia — bieżąca”, tylko na literach: a → k to 10 pól, k → o to 4, o → t to 5. Razem 19.

Pętla for (char z : s) to pętla „dla każdego znaku” z lekcji o napisach i vectorze.

Najmniejsza różnica: posortuj i patrz na sąsiadów

Dwie liczby z całego zbioru, które leżą najbliżej siebie — jak je znaleźć? Można sprawdzić wszystkie pary dwiema pętlami. Ale jest sprytniej: po posortowaniu najbliższa para zawsze stoi obok siebie. Dlaczego? Jeśli a ≤ b ≤ c, to odległość z a do c jest sumą odległości z a do b i z b do c — nie może więc być mniejsza od żadnej z nich. Para „przez kogoś” nigdy nie wygra z parą sąsiadów.

Liczby 14, 3, 9, 20, 11 po posortowaniu. Różnice sąsiadów: 6, 2, 3, 6 — najmniejsza 2, między 9 a 11.
najmniejsza_roznica.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    int naj = v[1] - v[0];
    for (int i = 2; i < n; i++) {
        naj = min(naj, v[i] - v[i - 1]);
    }
    cout << naj << "\n";
    return 0;
}
▶ Wejście
5 14 3 9 20 11
▶ Wyjście
2

Po sort każda liczba jest nie mniejsza od poprzedniej, więc v[i] - v[i - 1] nigdy nie jest ujemne — moduł nie jest tu potrzebny (choć nie zaszkodzi).

Ciekawostka: suma wszystkich różnic sąsiadów po posortowaniu to zawsze największa liczba minus najmniejsza (tu 6 + 2 + 3 + 6 = 17 = 20 − 3). Skoki po posortowanym ciągu „składają się” w jeden duży skok od początku do końca.

Sprawdź się w głowie

Najpierw wypisz sobie na kartce wszystkie skoki między sąsiadami, a dopiero potem kliknij „Pokaż odpowiedź”.

Ile pięter przejedzie winda?
int p[4] = {2, 6, 3, 3};
int s = 0;
for (int i = 1; i < 4; i++) s += abs(p[i] - p[i - 1]);
cout << s;
Pokaż odpowiedź
7Skoki: 4, 3 i 0 (postój na tym samym piętrze). Razem 7.
Co wypisze ten fragment?
int h[4] = {1, -4, 2, 0};
int naj = 0;
for (int i = 1; i < 4; i++) naj = max(naj, abs(h[i] - h[i - 1]));
cout << naj;
Pokaż odpowiedź
6Skoki: |−4 − 1| = 5, |2 − (−4)| = 6, |0 − 2| = 2. Największy to 6.
Co wypisze ten fragment?
int h[4] = {5, 8, 6, 9};
int g = 0, d = 0;
for (int i = 1; i < 4; i++) {
    int r = h[i] - h[i - 1];
    if (r > 0) g += r;
    else d -= r;
}
cout << g << " " << d;
Pokaż odpowiedź
6 2Zmiany: +3, −2, +3. Podejścia 3 + 3 = 6, zejścia 2 (d -= −2 dodaje 2).
Co wypisze ten fragment?
int v[4] = {7, 2, 9, 4};
sort(v, v + 4);
int s = 0;
for (int i = 1; i < 4; i++) s += v[i] - v[i - 1];
cout << s;
Pokaż odpowiedź
7Po sortowaniu 2, 4, 7, 9: skoki 2 + 3 + 2 = 7 — czyli największa minus najmniejsza, 9 − 2.
Co wypisze ten fragment?
int v[4] = {10, 4, 7, 15};
sort(v, v + 4);
int naj = v[1] - v[0];
for (int i = 2; i < 4; i++) naj = min(naj, v[i] - v[i - 1]);
cout << naj;
Pokaż odpowiedź
3Po sortowaniu 4, 7, 10, 15: różnice 3, 3, 5. Najmniejsza to 3.
Ile przesunięć palca (start na a)?
string s = "aba";
char p = 'a';
int r = 0;
for (char z : s) { r += abs(z - p); p = z; }
cout << r;
Pokaż odpowiedź
2a → a: 0, a → b: 1, b → a: 1. Razem 2.
Ile skoków jest większych od 2?
int a[6] = {0, 3, 4, 1, 1, 6};
int ile = 0;
for (int i = 1; i < 6; i++)
    if (abs(a[i] - a[i - 1]) > 2) ile++;
cout << ile;
Pokaż odpowiedź
3Skoki: 3, 1, 3, 0, 5. Większe od 2 są trzy: 3, 3 i 5.
Co wypisze program dla podanego wejścia?
int n, pop;
cin >> n >> pop;
int s = 0;
for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    s += abs(x - pop);
    pop = x;
}
cout << s;
Wejście: 4 1 4 -2 3
Pokaż odpowiedź
14Pierwsza liczba trafia do pop. Skoki: |4 − 1| = 3, |−2 − 4| = 6, |3 − (−2)| = 5. Razem 14.
Ć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 Trasa windyłatwe✓ zaliczone Winda rusza z parteru i zatrzymuje się na n przystankach. Ile pięter przejechała? abs(p[i] - p[i - 1])suma skokówstart z parteru Rozwiąż 5.2 Największy skokłatwe✓ zaliczone Największa różnica między sąsiednimi pomiarami i numer pomiaru, do którego nastąpił skok. skoki sąsiadówrekordremis: najwcześniejszy Rozwiąż 5.3 Gładki ciągłatwe✓ zaliczone Czy każdy skok między sąsiadami jest nie większy niż k? Jeśli nie — gdzie jest pierwszy za duży? abs(a[i] - a[i - 1]) <= kpierwsze złe miejscebreak Rozwiąż 5.4 Podejścia i zejściałatwe✓ zaliczone Szlak w górach: suma podejść, suma zejść i suma wszystkich zmian wysokości. różnica ze znakiemsuma modułówdwa liczniki Rozwiąż 5.5 Pisanie jednym palcemłatwe✓ zaliczone Klawiatura z literami a–z w jednym rzędzie. Ile przesunięć palca, żeby napisać słowo? abs(z - palec)stringstart na a Rozwiąż 5.6 Listonoszśrednie✓ zaliczone Trasa listonosza z poczty przez kolejne domy i z powrotem. A gdyby mógł wybrać kolejność? suma skokówstart i powrót do 0long long Rozwiąż 5.7 Najmniejsza różnica i ile razyśrednie✓ zaliczone Posortuj i patrz na sąsiadów: najmniejsza różnica dwóch liczb i liczba par, które ją mają. sortsąsiedzi po sortowaniuliczenie par Rozwiąż 5.8 Wstrząsyśrednie✓ zaliczone Sejsmograf: ile było wstrząsów (skoków większych od k) i jak długi był najdłuższy spokojny fragment? skoki sąsiadówserialiczenie Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Kroki po kratce — taksówkarz, król i romb z gwiazdek

Do tej pory wszystko działo się na jednej osi. Teraz wychodzimy na płaszczyznę — na kartkę w kratkę, mapę miasta albo szachownicę. Punkt ma tu dwie współrzędne: x (jak daleko w prawo) i y (jak wysoko). Jak daleko jest z punktu A do punktu B?

Wyobraź sobie miasto, w którym ulice tworzą idealną kratkę, jak na Manhattanie w Nowym Jorku. Skrzyżowania leżą w punktach o współrzędnych całkowitych. Taksówka nie przejedzie przez budynki na ukos — musi jechać ulicami: w poziomie i w pionie.

AB
Z A = (0, 0) do B = (5, 3) prowadzi wiele najkrótszych tras. Każda ma 5 odcinków w poziomie i 3 w pionie — razem 8.

Na rysunku są trzy różne trasy z A do B, ale wszystkie mają tę samą długość: 8. Każda najkrótsza trasa musi zrobić dokładnie 5 kroków w prawo (bo x zmienia się z 0 na 5) i dokładnie 3 kroki w górę (y z 0 na 3) — różni się tylko kolejnością. Krok w lewo albo w dół trzeba by potem „odrobić”, więc trasa byłaby dłuższa.

Liczba kroków w poziomie to odległość współrzędnych x: |x1 − x2|. W pionie: |y1 − y2|. Taką odległość nazywamy odległością miejską (albo odległością taksówkarza) — w lekcji o parach już ją liczyłeś.

odległość miejska = |x1 − x2| + |y1 − y2|
taksowka.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << abs(x1 - x2) + abs(y1 - y2) << "\n";
    return 0;
}
▶ Wejście 1
0 0 5 3
▶ Wyjście 1
8
▶ Wejście 2
-1000000000 -1000000000 1000000000 1000000000
▶ Wyjście 2
4000000000

Dwie odległości na osiach, dodane. Współrzędne mogą być ujemne — abs się tym zajmie.

Dlaczego long long? Gdy współrzędne sięgają miliarda, każda z dwóch odległości może mieć dwa miliardy, a ich suma — cztery miliardy. To nie mieści się w int. Tu pomaga pułapka 3 z części 3: odległość bywa dwa razy większa niż liczby, a suma dwóch odległości — cztery razy.

Król chodzi też na ukos

AB
Pomarańczowa: taksówka (albo wieża krokami po jednym polu) — 5 + 3 = 8 ruchów. Niebieska: król — 3 ruchy na ukos i 2 w bok, razem 5.

Król szachowy w jednym ruchu przechodzi na dowolne z ośmiu sąsiednich pól — także na ukos. Ruch na ukos zmienia naraz x i y, czyli „załatwia” jeden krok w poziomie i jeden w pionie za cenę jednego ruchu.

Z (0, 0) do (5, 3) król zrobi więc 3 ruchy na ukos (do (3, 3)) i jeszcze 2 w prawo: razem 5 ruchów. Ogólnie: tyle, ile wynosi większa z dwóch odległości.

ruchy króla = max(|x1 − x2|, |y1 − y2|)

Zobacz różnicę na planszy. Każde pole pokazuje swoją odległość od startu (białe pole z zerem). Przełącz miarę przyciskami u góry: pola o tej samej odległości miejskiej układają się w romby, a pola o tej samej odległości króla — w kwadraty. Kliknij pole, żeby zobaczyć rachunek, a kliknij je drugi raz, żeby przenieść tam start.

Plansza — kliknij dowolne pole
Ta ramka działa po włączeniu JavaScriptu.

Figury szachowe i moduły

Moduły różnic współrzędnych mówią bardzo dużo o ruchach figur szachowych. Oznaczmy dx = |x1 − x2| (o ile kolumn) i dy = |y1 − y2| (o ile wierszy). Wtedy dla dwóch różnych pól:

figuradojdzie w jednym ruchu, gdy…warunek w C++
wieżaten sam wiersz albo ta sama kolumnadx == 0 || dy == 0
goniecta sama przekątna — w bok tyle samo, co w górędx == dy
hetmanjak wieża albo jak goniecdx == 0 || dy == 0 || dx == dy
królpole tuż obok, także na ukosmax(dx, dy) == 1
skoczek„literka L”: 2 w jedną stronę i 1 w drugądx * dy == 2
szachy.cpp
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() {
    string a, b;                     // np. c1 i h6
    cin >> a >> b;
    int dx = abs(a[0] - b[0]);       // różnica kolumn (liter)
    int dy = abs(a[1] - b[1]);       // różnica wierszy (cyfr)
    cout << "goniec: " << (dx == dy ? "TAK" : "NIE") << "\n";
    cout << "skoczek: " << (dx * dy == 2 ? "TAK" : "NIE") << "\n";
    cout << "krol: " << max(dx, dy) << " ruchow\n";
    return 0;
}
▶ Wejście
c1 h6
▶ Wyjście
goniec: TAK skoczek: NIE krol: 5 ruchow

Pola na szachownicy opisuje się literą kolumny (a–h) i cyfrą wiersza (1–8). Nie musimy zamieniać ich na liczby od 1 do 8: odległość liter c i h to po prostu abs('c' - 'h') = 5, a odległość cyfr 1 i 6 to abs('1' - '6') = 5 — kody kolejnych liter i kolejnych cyfr też idą po kolei.

dx = 5 i dy = 5, więc pola leżą na jednej przekątnej i goniec przejdzie jednym ruchem. Skoczek nie (5 · 5 to nie 2), a król potrzebuje 5 ruchów.

Dlaczego skoczek to dx * dy == 2? Iloczyn dwóch liczb całkowitych nieujemnych równy 2 da się dostać tylko jako 1 · 2 albo 2 · 1 — dokładnie „literka L”.

Romb z gwiazdek jednym warunkiem

W lekcji o pętli for rysowałeś romb, licząc w każdym wierszu kropki i gwiazdki. Z modułem da się to zrobić jednym warunkiem. Ponumeruj wiersze i kolumny od −n do n, tak żeby środek rysunku miał współrzędne (0, 0). Wtedy abs(i) + abs(j) to odległość miejska pola od środka, a romb to wszystkie pola, które leżą od środka co najwyżej n kroków.

romb.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = -n; i <= n; i++) {
        for (int j = -n; j <= n; j++) {
            if (abs(i) + abs(j) <= n) cout << '*';
            else cout << '.';
        }
        cout << "\n";
    }
    return 0;
}
▶ Wejście
3
▶ Wyjście
...*... ..***.. .*****. ******* .*****. ..***.. ...*...

Sprawdźmy jeden wiersz. Dla i = −3 warunek to 3 + abs(j) <= 3, czyli tylko j = 0 — jedna gwiazdka w środku. Dla i = 0 warunek to abs(j) <= 3 — gwiazdka w każdej kolumnie.

Zmień jeden znak, a dostaniesz inny rysunek:

• abs(i) + abs(j) == n — sam kontur rombu,
• max(abs(i), abs(j)) == n — ramka kwadratu (odległość króla!),
• abs(i) == abs(j) — dwie przekątne, czyli litera X.

pierscienie.cpp
int n = 2;
for (int i = -n; i <= n; i++) {
    for (int j = -n; j <= n; j++) {
        cout << abs(i) + abs(j);
    }
    cout << "\n";
}
▶ Wyjście
43234 32123 21012 32123 43234
kwadraty.cpp
int n = 2;
for (int i = -n; i <= n; i++) {
    for (int j = -n; j <= n; j++) {
        cout << max(abs(i), abs(j));
    }
    cout << "\n";
}
▶ Wyjście
22222 21112 21012 21112 22222

Te dwa obrazki to „mapy odległości” od środka — dokładnie to, co pokazuje plansza wyżej. Z lewej odległość miejska: jedynki tworzą mały romb wokół zera, dwójki — większy. Z prawej odległość króla: każda liczba tworzy kwadratowy pierścień.

Sprawdź się w głowie

Najpierw policz w głowie — osobno różnicę w poziomie i w pionie — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile kroków zrobi taksówka z (1, 5) do (4, 1)?
cout << abs(1 - 4) + abs(5 - 1);
Pokaż odpowiedź
73 kroki w poziomie i 4 w pionie: razem 7.
Ile ruchów potrzebuje król z (2, 3) do (7, 1)?
int dx = abs(2 - 7), dy = abs(3 - 1);
cout << max(dx, dy);
Pokaż odpowiedź
5dx = 5, dy = 2. Dwa ruchy na ukos załatwiają pion, potem jeszcze 3 w bok: max(5, 2) = 5.
Czy goniec przejdzie z (3, 2) na (6, 5)?
int dx = abs(3 - 6), dy = abs(2 - 5);
cout << (dx == dy);
Pokaż odpowiedź
1dx = dy = 3 — pola leżą na jednej przekątnej.
Czy skoczek przejdzie z (4, 4) na (2, 5)?
int dx = abs(4 - 2), dy = abs(4 - 5);
cout << (dx * dy == 2);
Pokaż odpowiedź
1dx = 2, dy = 1 — literka L. Iloczyn 2.
Ile kolumn dzieli pola b i g?
char a = 'b', b = 'g';
cout << abs(a - b);
Pokaż odpowiedź
5Litery mają kolejne kody, więc od b do g jest 5 kolumn.
Ile pól ma ten romb?
int ile = 0;
for (int i = -2; i <= 2; i++)
    for (int j = -2; j <= 2; j++)
        if (abs(i) + abs(j) <= 2) ile++;
cout << ile;
Pokaż odpowiedź
13Wiersze rombu mają 1, 3, 5, 3 i 1 pole: razem 13.
A ile pól ma ten kształt?
int ile = 0;
for (int i = -2; i <= 2; i++)
    for (int j = -2; j <= 2; j++)
        if (max(abs(i), abs(j)) <= 1) ile++;
cout << ile;
Pokaż odpowiedź
9Pola co najwyżej 1 ruch króla od środka to kwadrat 3 × 3: 9 pól.
Co wypisze ten wiersz rysunku?
int n = 3, i = -1;
for (int j = -n; j <= n; j++) {
    if (abs(i) + abs(j) <= n) cout << '*';
    else cout << '.';
}
Pokaż odpowiedź
.*****.Dla i = −1 warunek to abs(j) <= 2: gwiazdki w kolumnach od −2 do 2, kropki na skrajach.
Ć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 Ulicami miastałatwe✓ zaliczone Odległość taksówkarza |x₁ − x₂| + |y₁ − y₂| dla punktów z dużymi współrzędnymi — w long long. odległość miejskaabs(dx) + abs(dy)long long Rozwiąż 6.2 Król kontra taksówkałatwe✓ zaliczone Ile ruchów potrzebuje król, a ile taksówka (tylko pion i poziom)? Policz obie odległości. max(|dx|, |dy|)|dx| + |dy|porównanie Rozwiąż 6.3 Wieża, goniec, hetmanśrednie✓ zaliczone Pola w notacji szachowej (np. c1 h6): czy wieża, goniec i hetman dojdą jednym ruchem? abs(a[0] - b[0])dx == dynotacja szachowa Rozwiąż 6.4 Ile ruchów ma skoczek?łatwe✓ zaliczone Na ile pól szachownicy skoczek może przejść z danego pola jednym ruchem? Sprawdź wszystkie 64. dx * dy == 2pętla po planszynotacja szachowa Rozwiąż 6.5 Kontur rombułatwe✓ zaliczone Narysuj sam brzeg rombu: gwiazdka tam, gdzie |i| + |j| = n, kropka wszędzie indziej. abs(i) + abs(j) == nrysowaniepętle od −n do n Rozwiąż 6.6 Kwadratowe pierścieniełatwe✓ zaliczone Na każdym polu cyfra max(|i|, |j|) — liczba ruchów króla ze środka. Wyjdą kwadratowe pierścienie. max(abs(i), abs(j))rysowanieodległość króla Rozwiąż 6.7 Ile pól w zasięgu?średnie✓ zaliczone Plansza h × w. Ile pól leży co najwyżej d kroków (w pionie i poziomie) od strażnika? odległość miejskadwie pętlebrzegi planszy Rozwiąż 6.8 Spotkanie na skrzyżowaniuśrednie✓ zaliczone Dwoje przyjaciół idzie naprzeciw siebie ulicami miasta. Po ilu minutach mogą być razem? odległość miejskadzielenie w góręlong long Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

„Co najwyżej o r” — przedziały, tolerancja i tarcza zamka

Na opakowaniu mąki jest napisane: 500 g ± 5 g. Znaczy to, że paczka może ważyć trochę mniej albo trochę więcej niż 500 g, ale różnica nie może przekroczyć 5 g. Paczka 497 g jest w porządku, 506 g — już nie. Taka dopuszczalna różnica nazywa się tolerancją.

„Różni się od 500 co najwyżej o 5” to po prostu „leży co najwyżej 5 kroków od 500”, czyli abs(x - 500) <= 5. Na osi to cały odcinek liczb od 495 do 505.

49049149249349449549649749849950150250350450550650750850951055500wzorzec
Wagi x, dla których |x − 500| ≤ 5: od 495 do 505. Środek to 500, a „promień” — 5 w każdą stronę.

Ogólnie: liczby x, które leżą co najwyżej r od środka c, tworzą przedział od c − r do c + r. Warunek z modułem i warunek z dwiema nierównościami znaczą dokładnie to samo:

|x − c| ≤ r  ⟺  c − r ≤ x ≤ c + r

W C++ możesz więc napisać abs(x - c) <= r albo c - r <= x && x <= c + r — wybierz zapis, który lepiej pasuje do treści zadania. Gdy zadanie mówi o środku i odchyleniu („500 ± 5”), wygodniejszy jest moduł. Gdy podaje dwa końce („od 495 do 505”) — dwie nierówności.

Za lekki, za ciężki czy w normie?

kontrola.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int c, r, x;          // wzorzec, tolerancja, waga paczki
    cin >> c >> r >> x;
    if (abs(x - c) <= r) {
        cout << "OK\n";
    } else if (x < c) {
        cout << "ZA LEKKA\n";
    } else {
        cout << "ZA CIEZKA\n";
    }
    return 0;
}
▶ Wejście 1
500 5 497
▶ Wyjście 1
OK
▶ Wejście 2
500 5 492
▶ Wyjście 2
ZA LEKKA
▶ Wejście 3
500 5 506
▶ Wyjście 3
ZA CIEZKA

Moduł odpowiada na pytanie „jak daleko od wzorca?”, ale gubi informację „w którą stronę”. Gdy paczka nie mieści się w normie, kierunek odczytujemy osobno, ze zwykłego porównania x < c.

Przypadki brzegowe: 495 i 505 są jeszcze w normie, bo warunek ma <=. Gdyby zadanie mówiło „mniej niż 5 g różnicy”, napisalibyśmy < — i wtedy 495 oraz 505 byłyby już złe. Zawsze czytaj, czy koniec przedziału się liczy.

Ile liczb mieści się w przedziale?

przedzial.cpp
int c = 10, r = 3;
int ile = 0;
for (int x = c - r; x <= c + r; x++) {
    cout << x << " ";
    ile++;
}
cout << "\n" << ile << " = " << 2 * r + 1 << "\n";
▶ Wyjście
7 8 9 10 11 12 13 7 = 7

Liczb całkowitych x z |x − c| ≤ r jest zawsze 2r + 1: r z lewej strony środka, r z prawej i sam środek. To ten sam rachunek co w części 1 dla |x| ≤ k — tam środkiem było zero.

A przy ostrej nierówności |x − c| < r? Końce c − r i c + r odpadają, więc zostaje 2r − 1 liczb (dla r ≥ 1).

Pętla wypisująca przedział idzie od c - r do c + r — nie trzeba sprawdzać modułu dla każdej liczby z osobna.

Równania z modułem

Jakie liczby x spełniają |x − 4| = 3? To liczby, które leżą dokładnie 3 kroki od 4: jedna w lewo (1) i jedna w prawo (7). Tak samo jak |x| = k z części 1, tylko środkiem jest 4 zamiast zera.

−10235689d = 3d = 34a1a − d7a + d
|x − 4| = 3 ma dwa rozwiązania: 4 − 3 = 1 i 4 + 3 = 7.
rownanie_a_d.cpp
#include <iostream>
using namespace std;

int main() {
    int a, d;              // |x - a| = d
    cin >> a >> d;
    if (d > 0) cout << 2 << "\n" << a - d << " " << a + d << "\n";
    else if (d == 0) cout << 1 << "\n" << a << "\n";
    else cout << 0 << "\n";
    return 0;
}
▶ Wejście 1
4 3
▶ Wyjście 1
2 1 7
▶ Wejście 2
-2 0
▶ Wyjście 2
1 -2

Program wypisuje liczbę rozwiązań i same rozwiązania rosnąco. Trzy przypadki, jak w części 1: dwa rozwiązania dla d > 0, jedno dla d = 0, zero dla d < 0.

A |x − a| = |x − b|? Szukamy liczby, która jest tak samo daleko od a i od b. To środek odcinka: (a + b) / 2. Na przykład dla 3 i 7 — liczba 5. Uwaga: gdy a + b jest nieparzyste (np. 3 i 8), środek wypada w połowie między liczbami całkowitymi (5,5), więc wśród liczb całkowitych rozwiązania nie ma. A gdy a = b, pasuje każda liczba.

Czy dwa zasięgi się stykają?

012356789101113141516|c1 − c2| = 8r1 = 3r2 = 34c112c2
Nadajniki w 4 i 12, zasięgi 3 i 3: zasięg pierwszego to 1–7, drugiego 9–15. Środki są 8 od siebie, a zasięgi sięgają razem tylko 3 + 3 = 6 — przerwa.

Przy prostej drodze stoją dwa nadajniki radiowe. Pierwszy w punkcie c1 i nadaje na odległość r1, drugi w c2 z zasięgiem r2. Czy na całym odcinku między nimi jest zasięg?

Pomyśl o odległości środków: |c1 − c2|. Pierwszy zasięg „pokrywa” r1 tej drogi, drugi — r2. Jeśli razem pokrywają całą odległość, zasięgi się stykają albo nachodzą:

przedziały się stykają ⟺ |c1 − c2| ≤ r1 + r2

W przeciwnym razie między nimi zostaje dziura długości |c1 − c2| − r1 − r2.

Tolerancja w procentach — bez liczb z przecinkiem

procenty.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long w, p, x;       // wzorzec, procent, pomiar
    cin >> w >> p >> x;
    if (abs(x - w) * 100 <= p * w) cout << "TAK\n";
    else cout << "NIE\n";
    return 0;
}
▶ Wejście 1
250 4 260
▶ Wyjście 1
TAK
▶ Wejście 2
250 4 261
▶ Wyjście 2
NIE

Często tolerancja jest podana w procentach: „pomiar może różnić się od wzorca co najwyżej o p%”. Dla wzorca 250 i 4% to 10, bo 4% z 250 = 10.

Warunek abs(x - w) <= p * w / 100.0 wymaga liczb z przecinkiem — a z lekcji o zaokrąglaniu wiesz, że te bywają zdradliwe. Lepiej pomnożyć obie strony przez 100: abs(x - w) * 100 <= p * w. Same liczby całkowite, żadnych przybliżeń.

A gdy liczby z przecinkiem są nie do uniknięcia — porównujesz je przez abs(a - b) < 1e-9, jak w lekcji o zaokrąglaniu. To też tolerancja: „różnią się mniej niż o włos”.

Odległość na tarczy: zamek, zegar, okrągły stół

Kłódka rowerowa ma kółka z cyframi od 0 do 9. Kółko można obracać w obie strony, a po 9 znowu jest 0. Ile obrotów o jedną cyfrę potrzeba, żeby z 1 zrobić 8? Kręcąc w górę: 1 → 2 → … → 8, to 7 obrotów. Ale kręcąc w dół: 1 → 0 → 9 → 8 — tylko 3!

012345678973
Z 1 do 8: w górę 7, w dół 3. Razem zawsze 10 — tyle, ile liczb na tarczy.

Na tarczy z n liczbami z a do b prowadzą zawsze dwie drogi. Jedna ma długość d = |a − b| — to droga „bez przechodzenia przez zero”. Druga obchodzi tarczę z drugiej strony i ma n − d, bo obie drogi razem dają pełny obrót.

Krótsza z nich to odległość na tarczy:

odległość na tarczy = min(d, n − d), gdzie d = |a − b|

Tak samo działa zegar (n = 12 godzin albo 60 minut), okrągły stół z n krzesłami i bieżnia, która zamyka się w pętlę.

tarcza.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int n = 10;               // cyfry od 0 do 9
    int d = abs(a - b);
    cout << min(d, n - d) << "\n";
    return 0;
}
▶ Wejście 1
1 8
▶ Wyjście 1
3
▶ Wejście 2
2 6
▶ Wyjście 2
4
▶ Wejście 3
0 9
▶ Wyjście 3
1

Dla 2 i 6 krótsza jest zwykła droga: 4 (druga ma 6). Dla 0 i 9 — droga „przez zero”: 1 obrót (zwykła ma 9).

Cała kłódka z kilkoma kółkami? Każde kółko obraca się osobno, więc liczymy odległość na tarczy dla każdego kółka i dodajemy — to jedno z ćwiczeń poniżej.

Na okrągłym stole krzesła mają zwykle numery od 1 do n, a nie od 0. Nic nie szkodzi: różnica |a − b| i wzór min(d, n - d) działają tak samo.

Sprawdź się w głowie

Najpierw odpowiedz w głowie — narysuj sobie przedział albo tarczę — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int c = 50, r = 3, x = 47;
cout << (abs(x - c) <= r);
Pokaż odpowiedź
1|47 − 50| = 3 ≤ 3 — koniec przedziału się liczy.
A ten?
int c = 50, r = 3, x = 46;
cout << (abs(x - c) <= r);
Pokaż odpowiedź
0|46 − 50| = 4 > 3 — poza przedziałem od 47 do 53.
Ile liczb policzy ten fragment?
int ile = 0;
for (int x = 0; x <= 20; x++)
    if (abs(x - 10) <= 4) ile++;
cout << ile;
Pokaż odpowiedź
9Od 6 do 14: 2 · 4 + 1 = 9 liczb.
Jakie są rozwiązania |x − 5| = 2?
int a = 5, d = 2;
cout << a - d << " " << a + d;
Pokaż odpowiedź
3 7Dwie liczby 2 kroki od 5: z lewej 3, z prawej 7.
Czy zasięgi się stykają?
int c1 = 0, r1 = 3, c2 = 10, r2 = 6;
cout << (abs(c1 - c2) <= r1 + r2);
Pokaż odpowiedź
0Środki są 10 od siebie, a zasięgi razem sięgają tylko 9. Zostaje dziura długości 1.
Czy pomiar mieści się w 5% tolerancji?
int w = 200, p = 5, x = 209;
cout << (abs(x - w) * 100 <= p * w);
Pokaż odpowiedź
15% z 200 to 10, a pomiar różni się o 9. W liczbach całkowitych: 900 ≤ 1000.
Ile obrotów kółka kłódki z 9 na 2?
int a = 9, b = 2, n = 10;
int d = abs(a - b);
cout << min(d, n - d);
Pokaż odpowiedź
3Zwykła droga ma 7, a przez zero: 9 → 0 → 1 → 2, czyli 3.
Która liczba jest tak samo daleko od 3 i od 7?
int a = 3, b = 7;
if ((a + b) % 2 == 0) cout << (a + b) / 2;
else cout << "BRAK";
Pokaż odpowiedź
5Środek odcinka od 3 do 7: |5 − 3| = |5 − 7| = 2.
Ć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 Kontrola jakościłatwe✓ zaliczone Paczki o wadze wzorzec ± tolerancja: OK, ZA LEKKA albo ZA CIEZKA dla każdej paczki. abs(x - c) <= rkierunek osobnokoniec się liczy Rozwiąż 7.2 Liczby wokół środkałatwe✓ zaliczone Wypisz, ile jest liczb całkowitych x z |x − c| ≤ r, i wszystkie te liczby rosnąco. od c − r do c + r2r + 1pętla Rozwiąż 7.3 Równanie |x − a| = dłatwe✓ zaliczone Liczby leżące dokładnie d od a: dwie, jedna albo żadna. Wypisz je rosnąco. a − d i a + dtrzy przypadkirozwiązania rosnąco Rozwiąż 7.4 Tak samo dalekośrednie✓ zaliczone Która liczba całkowita leży tak samo daleko od a i od b? Środek odcinka — o ile istnieje. (a + b) / 2parzystość sumyprzypadek a = b Rozwiąż 7.5 Tolerancja w procentachśrednie✓ zaliczone Czy pomiar różni się od wzorca co najwyżej o p procent? Same liczby całkowite, bez double. abs(x - w) * 100 <= p * wlong longbez liczb z przecinkiem Rozwiąż 7.6 Dwa nadajnikiśrednie✓ zaliczone Czy zasięgi dwóch nadajników przy drodze się stykają? Jeśli nie — jak długa jest dziura? |c1 − c2| ≤ r1 + r2przedziałydziura między zasięgami Rozwiąż 7.7 Okrągły stółłatwe✓ zaliczone n krzeseł dookoła stołu. O ile krzeseł przesunąć się z a do b, idąc krótszą drogą? min(d, n - d)odległość na tarczynumery od 1 Rozwiąż 7.8 Zamek szyfrowyśrednie✓ zaliczone Kłódka z kółkami 0–9: ile najmniej obrotów, żeby z jednego kodu zrobić drugi? min(d, 10 - d)string cyfrsuma po kółkach Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Gdzie się spotkać? Suma odległości i mediana

Pięcioro przyjaciół mieszka przy jednej długiej ulicy, w domach numer 1, 3, 4, 9 i 12 (numer to zarazem pozycja na osi). Chcą się spotkać w jednym punkcie p i każdy dojdzie tam pieszo. Gdzie powinni się umówić, żeby wszyscy razem przeszli jak najmniej?

Osoba z domu x przejdzie |x − p|. Razem przejdą sumę odległości: |1 − p| + |3 − p| + |4 − p| + |9 − p| + |12 − p|. Ta suma zależy od p — i szukamy p, dla którego jest najmniejsza.

02578101113532361349126p
Spotkanie w p = 6: 5 + 3 + 2 + 3 + 6 = 19 kroków razem.

Policzmy dla kilku miejsc

suma_odleglosci.cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int domy[5] = {1, 3, 4, 9, 12};
    for (int p = 2; p <= 7; p++) {
        int suma = 0;
        for (int i = 0; i < 5; i++) {
            suma += abs(domy[i] - p);
        }
        cout << "p = " << p << ": " << suma << "\n";
    }
    return 0;
}
▶ Wyjście
p = 2: 21 p = 3: 18 p = 4: 17 p = 5: 18 p = 6: 19 p = 7: 20

Najprostsza metoda: dla każdego kandydata p policz sumę odległości pętlą i zobacz, który wypada najlepiej. Wychodzi, że najlepsze jest p = 4 — suma 17.

Zaskoczenie? Średnia pozycja domów to (1 + 3 + 4 + 9 + 12) / 5 = 5,8 — a spotkanie w 6 kosztuje 19, więcej niż w 4. Najlepszym miejscem okazał się dom stojący w środku: dwa domy są na lewo od niego (1 i 3), dwa na prawo (9 i 12).

Przesuwaj suwak w ramce poniżej i obserwuj wykres. Potem kliknij „Nowe domy” albo „Dodaj dom” — czy najlepsze miejsce zawsze wypada w środkowym domu?

Gdzie się spotkać? — przesuwaj miejsce zbiórki
Ta ramka działa po włączeniu JavaScriptu.

Dlaczego środek? Krok w prawo, krok w lewo

Wyobraź sobie, że stoisz w punkcie p i przesuwasz miejsce spotkania o jeden krok w prawo. Każdy, kto mieszka na prawo od p, będzie miał o 1 bliżej. Każdy, kto mieszka na lewo (albo dokładnie w p), będzie miał o 1 dalej. Suma zmieni się więc o (liczba osób z lewej) − (liczba osób z prawej).

Dopóki po prawej stronie mieszka więcej osób niż po lewej, krok w prawo się opłaca. Gdy po lewej robi się więcej — przestaje. Najlepsze miejsce jest tam, gdzie po obu stronach jest „tyle samo” ludzi — w środkowym domu. Środkowy element posortowanego ciągu nazywamy medianą (znasz ją z lekcji o sortowaniu).

Suma odległości jest najmniejsza w medianie Suma |x₁ − p| + |x₂ − p| + … + |xₙ − p| jest najmniejsza, gdy p to mediana liczb x. Posortuj liczby i weź x[n / 2]. Przy parzystym n równie dobre jest każde p między dwiema środkowymi liczbami, w tym x[n / 2 - 1] i x[n / 2].
zbiorka.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    sort(x.begin(), x.end());
    long long m = x[n / 2];             // mediana
    long long suma = 0;
    for (int i = 0; i < n; i++) {
        suma += abs(x[i] - m);
    }
    cout << m << " " << suma << "\n";
    return 0;
}
▶ Wejście 1
5 9 1 12 3 4
▶ Wyjście 1
4 17
▶ Wejście 2
4 12 1 9 3
▶ Wyjście 2
9 17

Program sortuje pozycje, bierze środkową i liczy sumę odległości od niej. Nie trzeba sprawdzać wszystkich kandydatów.

Drugie wejście ma parzyście wiele domów: 1, 3, 9, 12. Środkowe są dwa: 3 i 9. Program wziął x[4 / 2] = x[2] = 9 i dostał 17. Gdyby wziął 3, też dostałby 17: |1 − 3| + 0 + |9 − 3| + |12 − 3| = 2 + 6 + 9 = 17. A dla p = 6: 5 + 3 + 3 + 6 = 17. Na całym odcinku między środkowymi domami suma jest taka sama — wykres w ramce ma tam płaskie dno.

Typ long long: tysiące odległości po miliardzie dają sumę dużo większą od zakresu int.

Mediana, nie średnia

0304050607080901020mediana10043średnia
srednia_czy_mediana.cpp
int x[3] = {10, 20, 100};
int sr = (10 + 20 + 100) / 3;      // 43
int med = 20;
int sumaSr = 0, sumaMed = 0;
for (int i = 0; i < 3; i++) {
    sumaSr += abs(x[i] - sr);
    sumaMed += abs(x[i] - med);
}
cout << sumaSr << " " << sumaMed << "\n";
▶ Wyjście
113 90

Dwóch kolegów mieszka blisko siebie (10 i 20), a trzeci daleko (100). Średnia pozycja to około 43 — tam spotkanie kosztowałoby 33 + 23 + 57 = 113 kroków. W medianie (20) tylko 10 + 0 + 80 = 90.

Średnia „daje się przeciągnąć” jednej dalekiej liczbie. Mediana nie: gdyby trzeci kolega mieszkał w 1000, mediana dalej byłaby w 20. Dlatego przy sumie odległości zawsze myśl o medianie.

Średnia też ma swoje zadanie: robi najmniejszą sumę kwadratów odległości. Ale to już temat na inną lekcję.

Wyrównywanie wież

wieze.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h.begin(), h.end());
    int cel = h[n / 2];
    long long ruchy = 0;
    for (int i = 0; i < n; i++) ruchy += abs(h[i] - cel);
    cout << ruchy << "\n";
    return 0;
}
▶ Wejście
4 3 8 5 1
▶ Wyjście
9

Masz n wież z klocków o wysokościach 3, 8, 5 i 1. W jednym ruchu możesz dołożyć jeden klocek na dowolną wieżę albo zdjąć jeden z dowolnej wieży. Ile najmniej ruchów potrzeba, żeby wszystkie wieże miały tę samą wysokość?

To przebrana zbiórka! Wybieramy docelową wysokość p, a wieża o wysokości h potrzebuje |h − p| ruchów. Suma jest najmniejsza dla mediany. Posortowane: 1, 3, 5, 8 — każda wysokość od 3 do 5 daje 9 ruchów (dla p = 5: 4 + 2 + 0 + 3 = 9).

Zbiórka na mapie miasta

miasto.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> xs(n), ys(n);
    for (int i = 0; i < n; i++) cin >> xs[i] >> ys[i];
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    long long px = xs[n / 2], py = ys[n / 2];
    long long suma = 0;
    for (int i = 0; i < n; i++) {
        suma += abs(xs[i] - px) + abs(ys[i] - py);
    }
    cout << px << " " << py << " " << suma << "\n";
    return 0;
}
▶ Wejście
3 0 0 2 5 4 1
▶ Wyjście
2 1 9

A gdy domy stoją na mapie miasta i chodzimy ulicami, jak taksówka z części 6? Odległość miejska to |x − px| + |y − py| — część „pozioma” zależy tylko od px, a „pionowa” tylko od py. Możemy więc wybrać je osobno: px to mediana wszystkich współrzędnych x, a py — mediana wszystkich y.

Uwaga: współrzędne x i współrzędne y sortujemy niezależnie, więc po sortowaniu xs[i] i ys[i] zwykle nie należą już do tego samego domu. Do sumy to nie przeszkadza — dodajemy wszystkie części poziome i wszystkie pionowe, w dowolnej kolejności.

Dla domów (0, 0), (2, 5), (4, 1): mediana x to 2, mediana y to 1. Suma: (2 + 1) + (0 + 4) + (2 + 0) = 9.

Sprawdź się w głowie

Najpierw policz w głowie — wypisz odległości od każdego domu — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int x[3] = {2, 5, 9}, p = 5, s = 0;
for (int i = 0; i < 3; i++) s += abs(x[i] - p);
cout << s;
Pokaż odpowiedź
73 + 0 + 4 = 7. Spotkanie w środkowym domu.
A dla p = 6?
int x[3] = {2, 5, 9}, p = 6, s = 0;
for (int i = 0; i < 3; i++) s += abs(x[i] - p);
cout << s;
Pokaż odpowiedź
84 + 1 + 3 = 8 — więcej niż w medianie (5).
Ile wynosi najmniejsza suma odległości?
int x[5] = {20, 4, 7, 1, 6};
sort(x, x + 5);
int m = x[2], s = 0;
for (int i = 0; i < 5; i++) s += abs(x[i] - m);
cout << s;
Pokaż odpowiedź
22Po sortowaniu 1, 4, 6, 7, 20 — mediana 6. Suma: 5 + 2 + 0 + 1 + 14 = 22.
Co wypisze ten fragment?
int x[4] = {2, 4, 10, 12};
int s1 = 0, s2 = 0;
for (int i = 0; i < 4; i++) {
    s1 += abs(x[i] - 4);
    s2 += abs(x[i] - 10);
}
cout << s1 << " " << s2;
Pokaż odpowiedź
16 16Przy parzystej liczbie domów każde miejsce między dwoma środkowymi (4 i 10) daje tę samą sumę: 16.
Średnia czy mediana?
int x[3] = {0, 0, 9};
int s1 = 0, s2 = 0;
for (int i = 0; i < 3; i++) {
    s1 += abs(x[i] - 3);     // średnia
    s2 += abs(x[i] - 0);     // mediana
}
cout << s1 << " " << s2;
Pokaż odpowiedź
12 9W średniej (3): 3 + 3 + 6 = 12. W medianie (0): 0 + 0 + 9 = 9. Mediana wygrywa.
Ile ruchów wyrówna wieże 4, 4 i 10?
int h[3] = {4, 4, 10};
int cel = 4, r = 0;
for (int i = 0; i < 3; i++) r += abs(h[i] - cel);
cout << r;
Pokaż odpowiedź
6Mediana to 4: trzeba zdjąć 6 klocków z najwyższej wieży.
Co wypisze ten fragment?
int x[3] = {1, 4, 6}, s = 0;
for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 3; j++)
        s += abs(x[i] - x[j]);
cout << s;
Pokaż odpowiedź
10Wszystkie pary: |1 − 4| = 3, |1 − 6| = 5, |4 − 6| = 2. Razem 10.
Ile przejdą razem mieszkańcy trzech domów do sklepu w (2, 1)?
int x[3] = {0, 2, 4}, y[3] = {0, 5, 1};
int s = 0;
for (int i = 0; i < 3; i++) s += abs(x[i] - 2) + abs(y[i] - 1);
cout << s;
Pokaż odpowiedź
9Dom (0, 0): 2 + 1 = 3. Dom (2, 5): 0 + 4 = 4. Dom (4, 1): 2 + 0 = 2. Razem 9.
Ć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 Ile przejdą razem?łatwe✓ zaliczone Suma odległości wszystkich domów od miejsca spotkania p — licz w long long. suma abs(x[i] - p)long longpętla Rozwiąż 8.2 Najlepsza propozycjałatwe✓ zaliczone Kilka propozycji miejsca zbiórki — wybierz tę z najmniejszą sumą odległości. pętla w pętlisuma odległościrekord Rozwiąż 8.3 Zbiórka przy ulicyśrednie✓ zaliczone Gdzie się spotkać, żeby przejść razem jak najmniej? Posortuj i weź medianę. sortmediana x[n / 2]long long Rozwiąż 8.4 Wszystkie najlepsze miejscaśrednie✓ zaliczone Przy parzystej liczbie domów najlepszych miejsc jest wiele. Wypisz pierwsze, ostatnie i ile ich jest. medianaparzyste nprzedział najlepszych miejsc Rozwiąż 8.5 Równe wieżeśrednie✓ zaliczone Dokładaj i zdejmuj klocki po jednym. Ile ruchów, żeby wszystkie wieże miały tę samą wysokość? medianasuma |h − cel|long long Rozwiąż 8.6 Sklep na osiedluśrednie✓ zaliczone Domy na mapie o ulicach w kratkę. Gdzie postawić sklep? Mediana x i mediana y — osobno. odległość miejskamediana osobno dla x i ylong long Rozwiąż 8.7 Średnia czy mediana?łatwe✓ zaliczone Łączna droga do średniej (zaokrąglonej w dół) i do mediany. Która propozycja wygrywa? średniamedianaporównanie Rozwiąż 8.8 Przystanek dla wiosekśrednie✓ zaliczone Wioski z różną liczbą mieszkańców. Gdzie postawić przystanek? Liczy się każdy mieszkaniec osobno. mediana ważonasortowanie parlong long Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Baza zadań: odległości w praktyce

Znasz już wszystkie narzędzia: moduł jako odległość od zera, if i funkcję abs z ich pułapkami, odległość dwóch liczb, rekord „najbliżej celu” z remisami, skoki między sąsiadami, odległość miejską i odległość króla, rysunki z modułem, przedziały i tolerancję, odległość na tarczy oraz medianę jako najlepsze miejsce zbiórki. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym, dwoma pomysłami, potem zadania średnie, a na końcu trudne — z wielkim finałem.

Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak sortowanie, sumy prefiksowe czy tablice dwuwymiarowe. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:

Ściąga: gotowe schematy

Moduł

if (x < 0) x = -x;   // ręcznie
x = abs(x);          // funkcja
abs(-7) / 2   // 3 (int)
abs(-7.0) / 2 // 3.5

Wynik ma typ argumentu. Pełny zakres int? Wczytaj do long long.

Odległość

abs(a - b)            // na osi
min(d, n - d)         // na tarczy
abs((int)s.size()
  - (int)t.size())

Kolejność odejmowania nie ma znaczenia. Różnica może być dwa razy większa od liczb.

Najbliżej celu

int d = abs(x - c);
if (d < najD ||
   (d == najD && x < naj)) {
    naj = x;  najD = d;
}

Porównuj odległości, zapamiętuj liczby. Remis: < — wcześniejsza, <= — późniejsza.

Sąsiedzi

for (int i = 1; i < n; i++)
    suma += abs(a[i] - a[i - 1]);
sort(v.begin(), v.end());
// najbliższa para = sąsiedzi

Suma skoków w long long. Po sortowaniu różnice są nieujemne.

Kratka i szachy

abs(dx) + abs(dy)     // taksówka
max(abs(dx), abs(dy)) // król
abs(dx) == abs(dy)    // goniec
dx * dy == 2          // skoczek

Rysunki: abs(i) + abs(j) <= n — romb, abs(i) == abs(j) — X.

Przedziały

abs(x - c) <= r
// c - r <= x && x <= c + r
// liczb całkowitych: 2r + 1
abs(c1 - c2) <= r1 + r2

Procenty bez double: abs(x - w) * 100 <= p * w.

Mediana

sort(x.begin(), x.end());
long long m = x[n / 2];
for (...) suma += abs(x[i] - m);

Najmniejsza suma odległości. Na mapie: osobno mediana x i mediana y.

Pułapki

abs(x);          // nic nie robi!
x % 10           // ujemne dla x < 0
abs(INT_MIN)     // dalej ujemne
s.size() - t.size() // bez minusa

Przed rozbieraniem na cyfry: x = abs(x); i osobno zero.

Jak rozwiązywać zadania z odległościami 1) Ustal, co jest odległością w zadaniu: kroki na osi, piętra, minuty, litery alfabetu, kroki po kratce, obroty tarczy? Narysuj to. 2) Sprawdź zakres: różnica dwóch dużych liczb albo suma wielu odległości może nie zmieścić się w int. 3) Gdy szukasz najbliższej liczby, przeczytaj regułę remisu i zapamiętuj liczbę, nie odległość. 4) Gdy pytanie brzmi „gdzie się spotkać” albo „do jakiej wartości wyrównać” — pomyśl o medianie. 5) Przetestuj skrajności: liczby ujemne, zero, równe liczby, końce przedziału i drogę „przez zero” na tarczy.
łatwe

Rozgrzewka · zadania 1–10

Jeden, dwa pomysły naraz: reszta czy dopłata, trzech przyjaciół, punktualność pociągów, ciepło-zimno, dwie windy, litera X, odległość od przedziału, spacer po osi, pomyłki synoptyka i fala na stawie.

1 Reszta czy dopłata?łatwe✓ zaliczone Klient zapłacił z groszy za zakupy za c groszy. Reszta, dopłata czy równo? abs(z - c)znak różnicyif Rozwiąż 2 Trzech przyjaciółłatwe✓ zaliczone Trzech przyjaciół przy jednej ulicy chce się spotkać i przejść razem jak najmniej. Ile przejdą? mediana trzech liczbmax − minsuma odległości Rozwiąż 3 Punktualność pociągówłatwe✓ zaliczone Opóźnienia pociągów (ujemne — przed czasem): ile pociągów było punktualnych i jakie było największe odstępstwo? abs(d) <= knajwiększy modułliczenie Rozwiąż 4 Ciepło, zimnołatwe✓ zaliczone Po każdym strzale podpowiedź: cieplej, zimniej, tak samo — albo TRAFIONY. abs(x - s)poprzedni strzałporównanie odległości Rozwiąż 5 Która winda przyjedzie?łatwe✓ zaliczone Dwie windy na poziomach e1 i e2. Przyjeżdża ta, która ma bliżej — przy remisie winda 1. abs(e - p)remisdwie odległości Rozwiąż 6 Litera Xłatwe✓ zaliczone Narysuj literę X w kwadracie: gwiazdka tam, gdzie |i| = |j|. abs(i) == abs(j)rysowanieprzekątne Rozwiąż 7 Odległość od odcinkałatwe✓ zaliczone Jak daleko jest punkt x od odcinka [a, b]? Zero, jeśli leży na nim, a w przeciwnym razie — do bliższego końca. przedziałbliższy koniecmin z dwóch odległości Rozwiąż 8 Spacer po osiłatwe✓ zaliczone Polecenia L k i P k. Jak daleko od startu jesteś na końcu, a jak daleko byłeś najdalej? pozycja ze znakiemabs(poz)long long Rozwiąż 9 Pomyłki synoptykałatwe✓ zaliczone Prognoza i prawdziwa temperatura przez n dni: łączna pomyłka, dzień największej pomyłki i dni bez pomyłki. suma modułówrekordliczenie zer Rozwiąż 10 Fala na stawiełatwe✓ zaliczone Kamień wpada w pole (r, c). Na każdym polu wypisz ostatnią cyfrę czasu |i − r| + |j − c|, po którym dojdzie tam fala. abs(i - r) + abs(j - c)rysowanie% 10 Rozwiąż
średnie

Średnie · zadania 11–20

Kilka pomysłów naraz: najbardziej podobny kolor, najbliższy kwadrat, podział taśmy, najbliższa stacja, spotkanie jak najszybciej, pole trójkąta, pary o różnicy k, wskazówki zegara, ranking rzutów i odległość od parku.

11 Najbardziej podobny kolorśrednie✓ zaliczone Kolor to trzy liczby R, G, B. Która farba z palety jest najbliżej szukanego koloru? suma trzech modułówrekordremis: mniejszy numer Rozwiąż 12 Najbliższy kwadratśrednie✓ zaliczone Dla każdej liczby n do 10¹² znajdź kwadrat liczby całkowitej, który leży najbliżej n. sqrt z poprawkądwóch kandydatówlong long Rozwiąż 13 Podział taśmyśrednie✓ zaliczone Przetnij taśmę z liczbami tak, żeby sumy obu kawałków różniły się jak najmniej. Sumy prefiksowe! sumy prefiksoweabs(lewa - prawa)long long Rozwiąż 14 Najbliższa stacjaśrednie✓ zaliczone Dla każdego kilometra autostrady: jak daleko do najbliższej stacji benzynowej? abs(i - j)min po stacjachdwa przejścia Rozwiąż 15 Spotkanie jak najszybciejśrednie✓ zaliczone Wszyscy idą naraz, po 1 na minutę. Po ilu minutach mogą być razem i w którym najmniejszym punkcie? max − mindzielenie w góręnajdalsi decydują Rozwiąż 16 Pole trójkątaśrednie✓ zaliczone Pole trójkąta z trzech punktów: moduł z jednego wyrażenia podzielony przez 2 — całkowite albo „i pół”. abs z wyrażenialong long.0 albo .5 Rozwiąż 17 Pary o różnicy kśrednie✓ zaliczone Ile jest par pozycji, na których liczby różnią się dokładnie o k? Sprawdź wszystkie pary. pary i < jabs(a[i] - a[j]) == kk = 0 Rozwiąż 18 Wskazówki zegaraśrednie✓ zaliczone Mniejszy kąt między wskazówkami o godzinie h:m. Licz w półstopniach, a na końcu wypisz .5, gdy trzeba. abs(60·h − 11·m)min(d, 720 − d)półstopnie Rozwiąż 19 Ranking rzutów do celuśrednie✓ zaliczone Posortuj zawodników według odległości rzutu od celu, a przy remisie alfabetycznie. sort z lambdąabs(x - T)remis: alfabet Rozwiąż 20 Odległość od parkuśrednie✓ zaliczone Park to prostokąt. Ile kroków (w pionie i poziomie) od domu do najbliższego punktu parku? odległość od przedziałuosobno x i ylong long Rozwiąż
trudne

Trudne · zadania 21–28

Dwie windy w akcji, najbliżsi na torze, stabilny fragment, pole działki, najbliższy palindrom, wszystkie odległości w mieście, kurier zachłanny — a na koniec wielki finał: teleturniej „Zgadnij liczbę”.

21 Dwie windy w akcjitrudne✓ zaliczone Symulacja: na każde wezwanie jedzie bliższa winda i zostaje na miejscu. Które windy jeździły i ile razem? symulacjaabs(w - p)remislong long Rozwiąż 22 Najbliżsi na torzetrudne✓ zaliczone Samochody na okrągłym torze. Najmniejsza odległość między dwoma z nich — pamiętaj o parze przez linię startu. sortsąsiedzi po sortowaniumin(d, L − d) Rozwiąż 23 Stabilny fragmenttrudne✓ zaliczone Najdłuższy fragment kolejnych pomiarów, w którym każde dwa różnią się co najwyżej o k. max − min ≤ kfragmentydwie pętle z przerwaniem Rozwiąż 24 Pole działkitrudne✓ zaliczone Pole wielokąta ze wzoru sznurowadłowego: suma iloczynów po kolejnych wierzchołkach, moduł i połowa. wzór sznurowadłowyabs na końculong long Rozwiąż 25 Najbliższy palindromtrudne✓ zaliczone Dla każdej liczby znajdź najbliższą liczbę-palindrom. Szukaj na zmianę w dół i w górę — przy remisie mniejsza. szukanie na zmianę w dół i w góręodwracanie liczbyremis: mniejszy Rozwiąż 26 Wszystkie odległości w mieścietrudne✓ zaliczone Suma odległości miejskich między wszystkimi parami domów — x i y osobno, z sortowaniem. osobno x i ysort i sumy prefiksowelong long Rozwiąż 27 Kurier zachłannytrudne✓ zaliczone Kurier zawsze jedzie pod najbliższy nieodwiedzony adres (odległość miejska). Wypisz kolejność i długość trasy. najbliższy nieodwiedzonytablica odwiedzinodległość miejskalong long Rozwiąż 28 Wielki finał: teleturniej „Zgadnij liczbę”trudne✓ zaliczone Punkty za bliskość strzału, premia dla najbliższych w rundzie i ranking z remisami — wszystko naraz. max(0, 10 − |strzał − sekret|)najbliżsi z remisamisort z lambdąpary i vector Rozwiąż

Częste błędy i dobre praktyki

📏
Moduł to odległość
|x| to odległość x od zera, a abs(a - b) — odległość a od b. Gdy nie wiesz, co policzyć, narysuj oś liczbową i policz kroki.
✍️
x = abs(x)
Samo abs(x); niczego nie zmienia — wynik przepada. Żeby zmienić zmienną, przypisz: x = abs(x);. To samo dotyczy -x.
🎯
Zapamiętuj oryginał
Gdy szukasz liczby najbliżej celu, porównuj odległości, ale zapisuj samą liczbę, ze znakiem. Zapisanie abs(x) gubi minus.
⚖️
Remisy
Dwie liczby mogą być tak samo blisko celu (8 i 12 przy celu 10). Warunek < zostawia wcześniejszą, <= bierze późniejszą. Zrób dokładnie to, co mówi zadanie.
💥
Różnica też ma zakres
Różnica dwóch liczb z zakresu int albo suma kilku odległości może nie zmieścić się w int. Gdy dane są duże, licz odległości w long long.
⚠️
Najmniejsza liczba int
abs(-2147483648) nie mieści się w int i zwykle wychodzi z powrotem ujemne. Gdy dane mogą mieć pełny zakres int, wczytuj je do long long.
📦
size() nie ma minusa
s.size() - t.size() nigdy nie jest ujemne — „przekręca się” na ogromną liczbę, a abs od niego się nie kompiluje. Pisz abs((int)s.size() - (int)t.size()).
➗
Reszta z liczby ujemnej
-1234 % 10 to −4. Ostatnią cyfrę bierz jako abs(x % 10), a przed rozbieraniem liczby na cyfry zrób x = abs(x);.
♟️
Taksówkarz czy król?
Ruchy tylko w pionie i poziomie: abs(dx) + abs(dy). Ruchy także na ukos: max(abs(dx), abs(dy)). Przekątna gońca: abs(dx) == abs(dy).
🎚️
„Co najwyżej o r”
abs(x - c) <= r znaczy dokładnie c - r <= x && x <= c + r. Liczb całkowitych w takim przedziale jest 2r + 1. Uważaj na < i <=.
🔄
Na tarczy są dwie drogi
Na kole z n liczbami (zamek, zegar, okrągły stół) z a do b są dwie drogi: d = abs(a - b) i n - d. Krótsza to min(d, n - d).
🏁
Mediana, nie średnia
Sumę odległości |x₁ − p| + … + |xₙ − p| najmniejszą robi mediana: posortuj i weź x[n / 2]. Średnia daje złą odpowiedź, gdy jedna liczba jest daleko od reszty.

Co dalej?

To była ostatnia lekcja drugiego etapu. Znasz już tablice, napisy, pary, vectory i sortowanie, a do tego cztery narzędzia matematyczne, które pojawiają się w zadaniach olimpijskich na każdym kroku: max i min, zaokrąglanie, silnię i wartość bezwzględną. Przed Tobą sprawdzian etapu — zestaw ZADANIA 2.0 — a potem trzeci etap, który zaczyna się od złożoności czasowej: nauczysz się szacować, czy Twój program zdąży w limicie czasu, zanim go uruchomisz. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.