Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Ten odcinek omawia dokładnie ten temat.
Co już umiesz i czego się nauczysz
Ta lekcja 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.
Odległość od zera
Oś liczbowa, |x| i liczby przeciwne, moduł przez if, funkcja abs, typy wyniku i trzy pułapki.
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.
Plansza i przedziały
Taksówkarz i król na kratce, figury szachowe, romb z gwiazdek, |x − c| ≤ r, tolerancja i tarcza zamka.
Gdzie się spotkać?
Suma odległości, dlaczego najlepsza jest mediana, a nie średnia, wyrównywanie wież i zbiórka na mapie miasta.
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.
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.
|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 |
|---|---|---|
| 7 | 7 | dodatnia — bez zmian |
| −7 | 7 | ujemna — bez minusa |
| 12 | 12 | dodatnia — bez zmian |
| −12 | 12 | ujemna — bez minusa |
| −1 | 1 | ujemna — bez minusa |
| 0 | 0 | zero leży w zerze |
| −250 | 250 | ujemna — bez minusa |
| 3000 | 3000 | dodatnia — 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ę.
Minus przed liczbą: liczba przeciwna
int x = -5;
cout << -x << "\n";
int y = 5;
cout << -y << "\n";
cout << -(-8) << "\n";
cout << x << " " << y << "\n";
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
#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;
}
| wczytane x | x < 0? | co robi program | wypisuje |
|---|---|---|---|
| −8 | tak | x = -x, czyli 8 | 8 |
| 3 | nie | nic nie zmienia | 3 |
| 0 | nie | nic nie zmienia | 0 |
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.
#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;
}
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?
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.
#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;
}
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
#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;
}
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.
|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;.
Najpierw odpowiedz w głowie — przy każdej zmiennej zapisz sobie, ile wynosi — a dopiero potem kliknij „Pokaż odpowiedź”.
int x = -6;
if (x < 0) x = -x;
cout << x;
Pokaż odpowiedź
int x = 9;
if (x < 0) x = -x;
cout << x;
Pokaż odpowiedź
int x = -3;
cout << -x << " " << x;
Pokaż odpowiedź
int x = 4;
x = -x;
x = -x;
cout << x;
Pokaż odpowiedź
int a = -5, b = 2;
if (a < 0) a = -a;
if (b < 0) b = -b;
cout << a + b;
Pokaż odpowiedź
int x = -7, z;
if (x > 0) z = 1;
else if (x < 0) z = -1;
else z = 0;
cout << z * 7;
Pokaż odpowiedź
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ź
int s = 0;
for (int x = -3; x <= 3; x++) {
if (x < 0) s -= x;
else s += x;
}
cout << s;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
#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;
}
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
int x = -5;
abs(x); // policzone... i wyrzucone
cout << x << "\n";
x = abs(x); // teraz zapisujemy wynik w x
cout << x << "\n";
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ł
| zapis | jak działa | kiedy używać |
|---|---|---|
if (x < 0) x = -x; | zmienia znak liczbie ujemnej | gdy 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łsz | spotkasz 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
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";
| wyrażenie (x = −4) | rachunek | wynik |
|---|---|---|
abs(x) + 1 | 4 + 1 | 5 |
2 * abs(x) | 2 · 4 | 8 |
abs(x - 3) | |−4 − 3| = |−7| | 7 |
abs(x) - 3 | 4 − 3 | 1 |
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
| a | b | |a| + |b| | |a + b| |
|---|---|---|---|
| 5 | 3 | 8 | 8 |
| −5 | −3 | 8 | 8 |
| 5 | −3 | 8 | 2 |
| −5 | 3 | 8 | 2 |
| 4 | −4 | 8 | 0 |
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
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
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
#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;
}
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
#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;
}
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.
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ć.
Najpierw policz w głowie — uważaj na nawiasy i na typy — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << abs(-12) + abs(5);
Pokaż odpowiedź
cout << abs(-12 + 5);
Pokaż odpowiedź
int x = -3;
abs(x);
cout << x;
Pokaż odpowiedź
cout << abs(-9) / 2 << " " << abs(-9.0) / 2;
Pokaż odpowiedź
int x = -4;
cout << abs(x - 3) << " " << abs(x) - 3;
Pokaż odpowiedź
cout << -abs(-6) << " " << abs(-(-6));
Pokaż odpowiedź
int x = -1234;
cout << x % 10 << " " << abs(x % 10);
Pokaż odpowiedź
int x = -7;
cout << max(x, -x) << " " << min(x, -x);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
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:
| a | b | a − b | b − a | |a − b| |
|---|---|---|---|---|
| 2 | 7 | −5 | 5 | 5 |
| 7 | 2 | 5 | −5 | 5 |
| −3 | 4 | −7 | 7 | 7 |
| −6 | −2 | −4 | 4 | 4 |
| 5 | 5 | 0 | 0 | 0 |
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.
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ą?
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
cout << abs(a - b) << "\n";
return 0;
}
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
| sytuacja | a | b | |a − b| |
|---|---|---|---|
| różnica wieku: Ala urodzona w 2012, Bartek w 2009 | 2012 | 2009 | 3 lata |
| temperatura: rano −4°C, w południe 5°C | −4 | 5 | 9 stopni |
| winda: z garażu −2 na piętro 5 | −2 | 5 | 7 pięter |
| wysokość: Rysy 2499 m, brzeg Morza Martwego około −430 m | 2499 | −430 | 2929 m |
| historia: Grunwald 1410, odsiecz wiedeńska 1683 | 1410 | 1683 | 273 lata |
| pozycje w tablicy: element 3 i element 11 | 3 | 11 | 8 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
#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;
}
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”
#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;
}
char a = 'c', b = 'k';
cout << abs(a - b) << "\n";
cout << abs('z' - 'a') << "\n";
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.
#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;
}
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
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
cout << abs(a - b) << "\n";
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
cout << abs(a - b) << "\n";
return 0;
}
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
string s = "kot", t = "hipopotam";
cout << abs(s.size() - t.size()) << "\n";
string s = "kot", t = "hipopotam";
cout << s.size() - t.size() << "\n";
string s = "kot", t = "hipopotam";
cout << abs((int)s.size() - (int)t.size()) << "\n";
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.
Najpierw policz w głowie — przy ujemnych liczbach narysuj sobie oś — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << abs(3 - 10) << " " << abs(10 - 3);
Pokaż odpowiedź
int a = -4, b = 6;
cout << abs(a - b);
Pokaż odpowiedź
int a = -4, b = -9;
cout << abs(a - b);
Pokaż odpowiedź
int p = 2, q = -3, r = 4;
cout << abs(p - q) + abs(q - r);
Pokaż odpowiedź
cout << abs('z' - 'a');
Pokaż odpowiedź
int a = 5, b = 1, c = 3;
cout << (abs(a - c) + abs(c - b) == abs(a - b));
Pokaż odpowiedź
int a = 5, b = 1, c = 7;
cout << abs(a - c) + abs(c - b) - abs(a - b);
Pokaż odpowiedź
int t1 = 8 * 60 + 50, t2 = 10 * 60 + 5;
cout << abs(t1 - t2);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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ść.
Porównuj odległości, zapamiętuj liczbę
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";
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";
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.
#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;
}
| x | |x − 10| | najlepsza po kroku |
|---|---|---|
| 12 | 2 | 12 (pierwsza) |
| 5 | 5 | 12 — 5 > 2 |
| 9 | 1 | 9 — 1 < 2 |
| 20 | 10 | 9 |
| 11 | 1 | 9 — remis, zostaje |
| 15 | 5 | 9 |
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 zadania | warunek podmiany |
|---|---|
| przy remisie wygrywa wcześniejsza | abs(x - c) < abs(naj - c) |
| przy remisie wygrywa późniejsza | abs(x - c) <= abs(naj - c) |
| przy remisie wygrywa mniejsza liczba | d < najD || (d == najD && x < naj) |
| przy remisie wygrywa większa liczba | d < najD || (d == najD && x > naj) |
#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;
}
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”
#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;
}
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
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
#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;
}
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.
Najpierw policz w głowie — wypisz sobie odległości wszystkich liczb od celu — a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
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ź
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ź
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ź
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ź
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ź
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ź
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ź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
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.
Suma skoków w programie
#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;
}
#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;
}
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.
| i | poprzednia | x | skok |x − poprzednia| | suma po kroku |
|---|---|---|---|---|
| 1 | 0 | 5 | 5 | 5 |
| 2 | 5 | 2 | 3 | 8 |
| 3 | 2 | −1 | 3 | 11 |
| 4 | −1 | 7 | 8 | 19 |
Największy skok
#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;
}
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ł
#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;
}
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
#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;
}
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.
#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;
}
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.
Najpierw wypisz sobie na kartce wszystkie skoki między sąsiadami, a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
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ź
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ź
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ź
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ź
string s = "aba";
char p = 'a';
int r = 0;
for (char z : s) { r += abs(z - p); p = z; }
cout << r;
Pokaż odpowiedź
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ź
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;
4 1 4 -2 3Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
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ś.
#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;
}
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
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.
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.
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:
| figura | dojdzie w jednym ruchu, gdy… | warunek w C++ |
|---|---|---|
| wieża | ten sam wiersz albo ta sama kolumna | dx == 0 || dy == 0 |
| goniec | ta sama przekątna — w bok tyle samo, co w górę | dx == dy |
| hetman | jak wieża albo jak goniec | dx == 0 || dy == 0 || dx == dy |
| król | pole tuż obok, także na ukos | max(dx, dy) == 1 |
| skoczek | „literka L”: 2 w jedną stronę i 1 w drugą | dx * dy == 2 |
#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;
}
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.
#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;
}
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.
int n = 2;
for (int i = -n; i <= n; i++) {
for (int j = -n; j <= n; j++) {
cout << abs(i) + abs(j);
}
cout << "\n";
}
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";
}
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ń.
Najpierw policz w głowie — osobno różnicę w poziomie i w pionie — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << abs(1 - 4) + abs(5 - 1);
Pokaż odpowiedź
int dx = abs(2 - 7), dy = abs(3 - 1);
cout << max(dx, dy);
Pokaż odpowiedź
int dx = abs(3 - 6), dy = abs(2 - 5);
cout << (dx == dy);
Pokaż odpowiedź
int dx = abs(4 - 2), dy = abs(4 - 5);
cout << (dx * dy == 2);
Pokaż odpowiedź
char a = 'b', b = 'g';
cout << abs(a - b);
Pokaż odpowiedź
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ź
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ź
int n = 3, i = -1;
for (int j = -n; j <= n; j++) {
if (abs(i) + abs(j) <= n) cout << '*';
else cout << '.';
}
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
„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.
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:
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?
#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;
}
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?
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";
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.
#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;
}
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ą?
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ą:
W przeciwnym razie między nimi zostaje dziura długości |c1 − c2| − r1 − r2.
Tolerancja w procentach — bez liczb z przecinkiem
#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;
}
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!
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:
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ę.
#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;
}
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.
Najpierw odpowiedz w głowie — narysuj sobie przedział albo tarczę — a dopiero potem kliknij „Pokaż odpowiedź”.
int c = 50, r = 3, x = 47;
cout << (abs(x - c) <= r);
Pokaż odpowiedź
int c = 50, r = 3, x = 46;
cout << (abs(x - c) <= r);
Pokaż odpowiedź
int ile = 0;
for (int x = 0; x <= 20; x++)
if (abs(x - 10) <= 4) ile++;
cout << ile;
Pokaż odpowiedź
int a = 5, d = 2;
cout << a - d << " " << a + d;
Pokaż odpowiedź
int c1 = 0, r1 = 3, c2 = 10, r2 = 6;
cout << (abs(c1 - c2) <= r1 + r2);
Pokaż odpowiedź
int w = 200, p = 5, x = 209;
cout << (abs(x - w) * 100 <= p * w);
Pokaż odpowiedź
int a = 9, b = 2, n = 10;
int d = abs(a - b);
cout << min(d, n - d);
Pokaż odpowiedź
int a = 3, b = 7;
if ((a + b) % 2 == 0) cout << (a + b) / 2;
else cout << "BRAK";
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
Policzmy dla kilku miejsc
#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;
}
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?
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).
|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].
#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;
}
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
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";
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ż
#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;
}
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
#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;
}
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.
Najpierw policz w głowie — wypisz odległości od każdego domu — a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
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ź
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ź
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ź
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ź
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ź
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ź
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ź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: 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.
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.
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.
Ś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.
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ę”.