C++ · Etap 2 · Lekcja 09

Pair — dwie wartości w jednym pudełku

Imię i liczba punktów. Godzina i minuta. Współrzędne x i y. Bardzo często dwie wartości należą do siebie i powinny trzymać się razem. Para — pair — skleja je w jedno pudełko z dwiema przegródkami: first i second. Zobaczysz, jak tworzyć pary, liczyć na punktach, godzinach, ułamkach i przedziałach, porównywać pary jak słowa w słowniku, trzymać je w tablicach, chodzić nimi po planszy i sortować jedną linijką. Na koniec rozwiążesz olimpijskie zadania z przedziałami i zdarzeniami. 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. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.

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 i String. Najbardziej przydadzą się tablice — zwłaszcza tablice równoległe i plansze — oraz porównywanie napisów, bo pary porównują się w bardzo podobny sposób.

Po co nam coś nowego? Przypomnij sobie z lekcji o tablicach zadanie z imionami i punktami. Imiona leżały w jednej tablicy, punkty w drugiej, a łączył je tylko ten sam numer pudełka. Działało, ale było kruche: zamieniasz miejscami dwóch uczniów — musisz pamiętać o zamianie w obu tablicach. Zapomnisz o jednej — i Kowalski dostaje punkty Nowaka. Para rozwiązuje ten problem raz na zawsze: imię i punkty leżą w jednym pudełku i zawsze podróżują razem.

Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw rozpisz sobie pary na kartce — osobno first i second — i odpowiedz w głowie, a dopiero potem sprawdzaj. Po każdej części rób ćwiczenia w sprawdzarce. Nie spiesz się i rób przerwy między częściami.

CZĘŚĆ 01–02

Pierwsza para i pary z życia

first i second, a potem punkty, godziny, ułamki i przedziały zapisane jako pary.

CZĘŚĆ 03–04

Porównywanie i tablice par

Pary porównane jak słowa w słowniku, sztuczka z minusem i rząd par zamiast dwóch tablic.

CZĘŚĆ 05–06

Rozpakowywanie i plansza

auto [a, b], pary w parach jako trójki i kierunki ruchu po planszy.

CZĘŚĆ 07–08

Sortowanie i olimpiada

Sortowanie par jedną linijką, ranking, przedziały i zdarzenia.

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 liczby:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane. Uważaj natomiast na spacje w środku wiersza, nawiasy, przecinki i dwukropki — gdy zadanie każe wypisać parę jako (3, 7), przecinek i spacja też się liczą.

Mapa lekcji

Para: jedno pudełko, dwie przegródki

Zacznijmy od problemu, który para rozwiązuje. W lekcji o tablicach trzymałeś imiona uczniów w jednej tablicy, a ich punkty w drugiej. Uczeń numer 0 to imię z pudełka imie[0] i punkty z pudełka punkty[0]. Wystarczy jednak jedna nieuwaga, żeby te dwie tablice się rozjechały. Zobacz:

rozjechane.cpp
string imie[2] = {"Ola", "Jan"};
int punkty[2] = {95, 87};
swap(imie[0], imie[1]);    // zamieniamy kolejność uczniów…
                           // …ale zapominamy o punktach!
cout << imie[0] << " " << punkty[0] << "\n";
cout << imie[1] << " " << punkty[1] << "\n";
▶ Wyjście — źle
Jan 95 Ola 87
razem.cpp
pair<string, int> u[2] = {{"Ola", 95}, {"Jan", 87}};
swap(u[0], u[1]);          // zamieniamy całych uczniów
cout << u[0].first << " " << u[0].second << "\n";
cout << u[1].first << " " << u[1].second << "\n";
▶ Wyjście
Jan 87 Ola 95

W lewym programie Jan nagle ma 95 punktów, które zdobyła Ola. Kompilator nie protestuje, bo z jego punktu widzenia to dwie niezależne tablice. W prawym programie imię i punkty siedzą w jednym pudełku — w parze — więc zamieniając pudełka, zamieniasz całych uczniów. Nie da się „zgubić” punktów po drodze. Nie przejmuj się, jeśli zapis po prawej wygląda na razie obco: w tej części rozbierzemy go na kawałki.

pair — jedno pudełko, dwie przegródki

Para to zmienna, która przechowuje dwie wartości naraz. Wyobraź sobie pudełko przedzielone na pół: w lewej przegródce leży jedna wartość, w prawej — druga. Lewa przegródka nazywa się first (pierwsza), a prawa second (druga). Parę tworzysz tak: pair<int, int> p;. W nawiasach ostrych podajesz dwa typy: typ przegródki first i typ przegródki second.

pair<int, int> p = {3, 7}; — jedno pudełko o nazwie p. W przegródce first leży 3, w przegródce second leży 7.
pierwsza_para.cpp
pair<int, int> p;      // para dwóch liczb int
p.first = 3;           // wkładamy 3 do pierwszej przegródki
p.second = 7;          // i 7 do drugiej
cout << p.first << " " << p.second << "\n";
cout << p.first + p.second << "\n";
▶ Wyjście
3 7 10

Do przegródki dostajesz się przez kropkę: p.first i p.second. Każda przegródka zachowuje się jak zwykła zmienna swojego typu — tutaj int. Możesz do niej coś wpisać, wypisać ją, dodawać, mnożyć, zwiększać przez ++.

Para jest w bibliotece <utility>, ale nie musisz jej osobno dołączać: wciąga ją już <iostream>, <string> i oczywiście <bits/stdc++.h>.

first i second piszesz bez nawiasów W lekcji o napisach pisałeś s.length() — z nawiasami, bo length to polecenie, które coś liczy. first i second to nie polecenia, tylko nazwy przegródek. Piszesz p.first, a nie p.first() — z nawiasami program się nie skompiluje.

Wartości od razu: klamry i make_pair

Wpisywanie każdej przegródki osobno jest długie. Parę możesz wypełnić od razu przy tworzeniu — wartości w klamrach, w kolejności: najpierw first, potem second. Drugi sposób to funkcja make_pair(a, b), która robi parę z dwóch wartości. Klamry działają też później, przy zwykłym przypisaniu — i to jest ważna różnica w porównaniu z tablicą, której klamrami później już nie wypełnisz.

klamry.cpp
pair<int, int> a = {3, 7};          // klamry przy tworzeniu
pair<int, int> b = make_pair(5, 1); // make_pair robi parę
pair<int, int> c;
c = {9, 2};                         // klamry działają też później
cout << a.first << " " << a.second << "\n";
cout << b.first << " " << b.second << "\n";
cout << c.first << " " << c.second << "\n";
▶ Wyjście
3 7 5 1 9 2

Wszystkie trzy sposoby dają taki sam rodzaj pary. Klamry są najkrótsze i to ich będziemy używać najczęściej. make_pair spotkasz w starszych programach i w internecie — dobrze go rozpoznawać.

Zapis c = {9, 2}; wymienia całą zawartość pary naraz: obie przegródki dostają nowe wartości w jednej linijce.

Różne typy w jednej parze

Przegródki pary nie muszą mieć tego samego typu. To jedna z największych zalet pary: w jednym pudełku zmieścisz imię i wiek, literę i liczbę, współrzędne z przecinkiem. Typy wpisujesz w nawiasach ostrych w tej samej kolejności, w jakiej potem podajesz wartości.

typy.cpp
pair<string, int> uczen = {"Ola", 95};
pair<char, int> ocena = {'A', 6};
pair<double, double> punkt = {1.5, -2.25};
pair<int, long long> duze = {3, 5000000000};
cout << uczen.first << " ma " << uczen.second << " pkt\n";
cout << ocena.first << ocena.second << "\n";
cout << punkt.first + punkt.second << "\n";
cout << duze.second * duze.first << "\n";
▶ Wyjście
Ola ma 95 pkt A6 -0.75 15000000000
zla_kolejnosc.cpp
pair<int, string> p = {"Ola", 95};   // BŁĄD: najpierw int, potem string!
▶ Kompilator
error: could not convert '{"Ola", 95}' from '<brace-enclosed initializer list>' to 'std::pair<int, std::__cxx11::basic_string<char> >'

Para pair<int, string> ma w first liczbę, a w second napis. Klamry {"Ola", 95} próbują włożyć napis do przegródki na liczbę — kompilator zgłasza błąd. Kolejność typów i kolejność wartości muszą do siebie pasować.

Nowa para ma zera

Pamiętasz śmieci w tablicy utworzonej wewnątrz main? Z parą tego problemu nie ma. Para utworzona bez wartości dostaje w każdej przegródce „zero” swojego typu: liczby dostają 0, napisy — pusty napis. Zawsze, nawet w środku main.

zera.cpp
pair<int, int> p;           // bez wartości
pair<string, int> q;        // też bez wartości
cout << p.first << " " << p.second << "\n";
cout << "[" << q.first << "] " << q.second << "\n";
▶ Wyjście
0 0 [] 0

p to para (0, 0), a q — para z pustym napisem i zerem. Nawiasy kwadratowe wokół q.first to znany z lekcji o napisach trik, dzięki któremu widać, że napis jest pusty.

Dzięki temu para świetnie nadaje się na licznik albo zbiornik na wynik: tworzysz ją bez wartości i od razu możesz zwiększać przegródki.

Wczytywanie i wypisywanie

Para nie umie wczytać się ani wypisać sama. cin >> p i cout << p się nie skompilują — trzeba pracować na przegródkach, jedna po drugiej. To dobra wiadomość: dzięki temu sam decydujesz, jak para ma wyglądać na ekranie.

wczytaj_wypisz.cpp
pair<int, int> p;
cin >> p.first >> p.second;
cout << "(" << p.first << ", " << p.second << ")\n";
cout << p.first << ":" << p.second << "\n";
▶ Wejście
4 9
▶ Wyjście
(4, 9) 4:9
cout_para.cpp
pair<int, int> p = {4, 9};
cout << p << "\n";          // BŁĄD: cout nie umie wypisać pary
▶ Kompilator
error: no match for 'operator<<' (operand types are 'std::ostream' and 'std::pair<int, int>')

Komunikat „no match for operator<<” znaczy: „nie wiem, jak wypisać coś takiego”. Gdy go zobaczysz przy parze, wypisz osobno p.first i p.second.

Kopia, porównanie i zamiana

Z parą jest tak wygodnie jak z napisem. Znak = robi pełną, osobną kopię. Znak == sprawdza, czy obie przegródki są takie same. A swap zamienia wartości miejscami — dwie przegródki jednej pary albo dwie całe pary.

kopia.cpp
pair<int, int> a = {1, 2};
pair<int, int> b = a;             // osobna kopia
b.second = 5;                     // zmieniamy tylko b
cout << a.second << " " << b.second << "\n";
cout << (a == b) << "\n";         // czy równe?
b.second = 2;
cout << (a == b) << "\n";
swap(a.first, a.second);          // zamiana wewnątrz pary
cout << a.first << " " << a.second << "\n";
▶ Wyjście
2 5 0 1 2 1
swap_pary.cpp
pair<string, int> x = {"Ola", 95};
pair<string, int> y = {"Jan", 87};
swap(x, y);                       // zamiana całych par
cout << x.first << " " << x.second << "\n";
cout << y.first << " " << y.second << "\n";
▶ Wyjście
Jan 87 Ola 95

Dwie pary są równe tylko wtedy, gdy równe są obie przegródki: first z first i second z second. Para (1, 2) i para (1, 5) nie są równe, choć mają ten sam first. A co z porównaniem „mniejsza — większa”? To osobna, bardzo ważna historia — poświęcimy jej całą część 3.

Zmiana jednej przegródki — prześledźmy

Ostatni przykład tej części pokazuje, że przegródki to zwykłe zmienne. Prześledź program w tabelce — w każdym wierszu fioletowa liczba to przegródka, która właśnie się zmieniła.

slad.cpp
pair<int, int> p = {4, 10};
p.first++;                  // 4 → 5
p.second -= p.first;        // 10 - 5 = 5
p.first *= 3;               // 5 * 3 = 15
p = {p.second, p.first};    // zamiana przez klamry
cout << p.first << " " << p.second << "\n";
▶ Wyjście
5 15
po linijcep.firstp.second
p = {4, 10}410
p.first++510
p.second -= p.first55
p.first *= 3155
p = {p.second, p.first}515

Ostatnia linijka to sprytna zamiana bez swap: C++ najpierw buduje nową parę z obecnych wartości (5, 15), a dopiero potem wkłada ją do p. Obie przegródki zmieniają się naraz.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
pair<int, int> p = {4, 9};
cout << p.second << p.first;
Pokaż odpowiedź
94Najpierw second (9), zaraz za nim first (4) — bez spacji.
Co wypisze ten fragment?
pair<int, int> p;
p.first = 5;
cout << p.first + p.second;
Pokaż odpowiedź
5Nowa para ma zera, więc p.second to 0. 5 + 0 = 5.
Co wypisze ten fragment?
pair<string, int> p = {"Ala", 3};
p.second *= 2;
cout << p.first << p.second;
Pokaż odpowiedź
Ala6second podwaja się do 6, a first zostaje „Ala”.
Kopia. Co wypisze ten fragment?
pair<int, int> a = {1, 2};
pair<int, int> b = a;
b.first = 7;
cout << a.first << b.first;
Pokaż odpowiedź
17b to osobna kopia — zmiana b.first nie rusza a.first.
Co wypisze ten fragment?
pair<int, int> p = {3, 8};
swap(p.first, p.second);
cout << p.first << " " << p.second;
Pokaż odpowiedź
8 3swap zamienia wartości przegródek miejscami.
Co wypisze ten fragment?
pair<int, int> a = {2, 5}, b = {2, 5};
cout << (a == b) << (a != b);
Pokaż odpowiedź
10Obie przegródki są równe, więc pary są równe: == daje 1, a != daje 0.
Para z literą. Co wypisze ten fragment?
pair<char, int> p = {'x', 3};
cout << string(p.second, p.first);
Pokaż odpowiedź
xxxstring(3, 'x') to napis z trzech liter x — przepis znasz z lekcji o napisach.
Co wypisze ten fragment?
pair<int, int> p = make_pair(6, 1);
p = {p.second, p.first};
cout << p.first << p.second;
Pokaż odpowiedź
16Nowa para powstaje z obecnych wartości: (1, 6). Wypisujemy 1 i 6 bez spacji.
Ć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 →

Pary z życia: punkty, godziny, ułamki, przedziały

Para to tylko pudełko z dwiema przegródkami — znaczenie nadajesz jej Ty. Te same dwie liczby mogą być punktem na mapie, godziną na zegarze, ułamkiem albo odcinkiem czasu. W tej części przejdziemy przez cztery najczęstsze „pary z życia” i przy okazji poznamy trzy małe, bardzo przydatne funkcje: abs, max i min. Przy każdej parze warto zostawić sobie komentarz, co oznacza first, a co second — po tygodniu sam tego nie będziesz pamiętał.

Punkt na płaszczyźnie: (x, y)

Punkt na kartce w kratkę opisują dwie liczby: x (jak daleko w prawo) i y (jak wysoko). To naturalna para: pair<int, int> a = {1, 2}; — a.first to x, a.second to y. Jak daleko są od siebie dwa punkty? Na olimpiadzie często liczy się odległość „taksówkarza” (zwaną też odległością miejską): taksówka nie jeździ na ukos, tylko wzdłuż ulic — najpierw w poziomie, potem w pionie. Odległość to różnica x plus różnica y, obie wzięte bez minusa.

„Bez minusa” załatwia funkcja abs(x) — wartość bezwzględna: abs(-5) to 5, a abs(3) to 3. Dzięki niej nie musisz się zastanawiać, który punkt jest bardziej na lewo.

taksowka.cpp
pair<int, int> a, b;          // first = x, second = y
cin >> a.first >> a.second >> b.first >> b.second;
int dx = abs(a.first - b.first);
int dy = abs(a.second - b.second);
cout << dx + dy << "\n";
▶ Wejście
1 2 4 -2
▶ Wyjście
7
srodek.cpp
pair<int, int> a = {1, 2}, b = {4, -2};
pair<double, double> s = {(a.first + b.first) / 2.0,
                          (a.second + b.second) / 2.0};
cout << s.first << " " << s.second << "\n";
a.first += 10;                // przesuwamy a o 10 w prawo
cout << a.first << " " << a.second << "\n";
▶ Wyjście
2.5 0 11 2

Z punktu (1, 2) do (4, −2) taksówka przejedzie 3 kratki w prawo i 4 w dół — razem 7. Środek odcinka to średnie współrzędnych. Dzielimy przez 2.0, a nie przez 2 — inaczej dzielenie liczb całkowitych obcięłoby 2,5 do 2 (pamiętasz pułapkę 7 / 2 z lekcji o typach?). Dlatego środek trzymamy w parze pair<double, double>.

Godzina: (godzina, minuta)

Godzina 13:45 to też para: {13, 45}. Jak dodać do niej 100 minut? Najprościej zamienić godzinę na liczbę minut od północy, dodać, a potem rozłożyć z powrotem na godziny i minuty — dzieleniem i resztą z dzielenia, jak w lekcji o modulo. Reszta z dzielenia przez 24 · 60 = 1440 dba o to, żeby po północy zegar zaczął liczyć od zera.

dodaj_minuty.cpp
pair<int, int> t = {13, 45};             // 13:45
int k = 100;                             // dodajemy 100 minut
int minuty = t.first * 60 + t.second + k;
minuty %= 24 * 60;                       // po północy znów od 0
t = {minuty / 60, minuty % 60};
cout << t.first << ":" << t.second << "\n";
▶ Wyjście
15:25
zegar.cpp
pair<int, int> t = {23, 50};             // 23:50
int m = (t.first * 60 + t.second + 15) % 1440;
t = {m / 60, m % 60};
if (t.first < 10) cout << "0";           // zera z przodu
cout << t.first << ":";
if (t.second < 10) cout << "0";
cout << t.second << "\n";
▶ Wyjście
00:05

13:45 to 825 minut od północy, plus 100 daje 925, a 925 minut to 15 godzin i 25 minut. W prawym programie 23:50 + 15 minut przekracza północ: 1445 % 1440 = 5, czyli 00:05. Zera z przodu dopisujemy sami — możesz też użyć setw(2) i setfill('0') z lekcji Input / Output.

Ułamek: (licznik, mianownik)

Ułamek ⅓ to para {1, 3}: first to licznik, second to mianownik. Dodawanie ułamków znasz ze szkoły: a/b + c/d = (a·d + c·b) / (b·d). Potem warto ułamek skrócić — podzielić licznik i mianownik przez ich największy wspólny dzielnik, liczony algorytmem Euklidesa z lekcji o modulo.

ulamki.cpp
pair<long long, long long> x = {1, 6}, y = {1, 3};
pair<long long, long long> s = {x.first * y.second + y.first * x.second,
                                x.second * y.second};
long long a = s.first, b = s.second;    // NWD — algorytm Euklidesa
while (b != 0) {
    long long r = a % b;
    a = b;
    b = r;
}
s = {s.first / a, s.second / a};        // skracamy przez NWD
cout << s.first << "/" << s.second << "\n";
▶ Wyjście
1/2

1/6 + 1/3 = (1 · 3 + 1 · 6) / 18 = 9/18. NWD(9, 18) to 9, więc po skróceniu wychodzi 1/2.

Dlaczego long long? Mnożenie mianowników szybko rośnie: dwa mianowniki po 100 000 dają 1010, za dużo dla int.

Ułamki porównujesz bez dzielenia, „na krzyż”: a/b < c/d dokładnie wtedy, gdy a · d < c · b (dla dodatnich mianowników). Dzielenie dałoby liczby z przecinkiem, a te bywają niedokładne.

Przedział: (od, do)

Przedział — odcinek na osi albo okres czasu — to para {początek, koniec}. Lekcja trwa od minuty 480 do 525, wycieczka od 3 do 8 lipca. Typowe pytania o przedział: jak jest długi, czy zawiera daną liczbę i czy nachodzi na inny przedział.

Do ostatniego pytania przydają się dwie gotowe funkcje: max(a, b) daje większą z dwóch liczb, a min(a, b) — mniejszą. Wspólna część dwóch przedziałów zaczyna się w późniejszym z początków i kończy we wcześniejszym z końców. Jeśli taki „przedział” ma początek za końcem — wspólnej części nie ma.

przedzialy.cpp
pair<int, int> a, b;
cin >> a.first >> a.second >> b.first >> b.second;
pair<int, int> w = {max(a.first, b.first), min(a.second, b.second)};
if (w.first <= w.second) {
    cout << w.first << " " << w.second << "\n";
} else {
    cout << "BRAK\n";
}
▶ Wejście
2 8 5 12
▶ Wyjście
5 8
▶ Inne wejście
2 4 6 9
▶ Wyjście
BRAK
Przedział a = [2, 8] i b = [5, 12] na osi liczb od 0 do 11. Niebieskie pola to wspólna część: od max(2, 5) = 5 do min(8, 12) = 8.

Dla [2, 4] i [6, 9]: max(2, 6) = 6, min(4, 9) = 4. Początek 6 leży za końcem 4 — przedziały się rozmijają, więc wypisujemy BRAK.

Długość przedziału to koniec - początek (albo o jeden więcej, gdy liczysz pełne dni od–do włącznie — zawsze czytaj treść uważnie). Czy przedział zawiera x? a.first <= x && x <= a.second.

abs, max i min abs(x) — liczba bez minusa. max(a, b) — większa z dwóch. min(a, b) — mniejsza z dwóch. Wszystkie trzy są w <bits/stdc++.h>. Uwaga: max i min chcą dwóch argumentów tego samego typu — max(x, 5LL) dla long long, a nie max(x, 5). W części 3 zobaczysz, że działają też na całych parach.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Odległość taksówkarza. Co wypisze ten fragment?
pair<int, int> a = {1, 5}, b = {4, 1};
cout << abs(a.first - b.first) + abs(a.second - b.second);
Pokaż odpowiedź
7Różnica x: |1 − 4| = 3. Różnica y: |5 − 1| = 4. Razem 7.
Co wypisze ten fragment?
cout << abs(-7) << abs(3);
Pokaż odpowiedź
73abs usuwa minus: 7, a 3 zostaje 3. Wypisane bez spacji.
Która będzie godzina?
pair<int, int> t = {9, 50};
int m = t.first * 60 + t.second + 20;
cout << m / 60 << ":" << m % 60;
Pokaż odpowiedź
10:109:50 to 590 minut, plus 20 daje 610 minut, czyli 10 godzin i 10 minut.
Co wypisze ten fragment?
cout << max(3, 8) << min(3, 8);
Pokaż odpowiedź
83max daje większą liczbę (8), min — mniejszą (3).
Wspólna część. Co wypisze ten fragment?
pair<int, int> a = {1, 4}, b = {3, 9};
cout << max(a.first, b.first) << " " << min(a.second, b.second);
Pokaż odpowiedź
3 4Wspólna część [1, 4] i [3, 9] to [3, 4]: późniejszy początek i wcześniejszy koniec.
Dodawanie ułamków 2/3 + 1/4. Co wypisze ten fragment?
pair<int, int> x = {2, 3}, y = {1, 4};
cout << x.first * y.second + y.first * x.second << "/" << x.second * y.second;
Pokaż odpowiedź
11/122 · 4 + 1 · 3 = 11, a 3 · 4 = 12. Ułamka 11/12 nie da się skrócić.
Gdzie skończy się punkt?
pair<int, int> p = {0, 0};
p.first += 3;
p.second -= 2;
p.first -= 1;
cout << p.first << "," << p.second;
Pokaż odpowiedź
2,-2x: 0 + 3 − 1 = 2, y: 0 − 2 = −2.
Czy przedział zawiera liczbę?
pair<int, int> a = {3, 6};
int x = 6;
cout << (a.first <= x && x <= a.second);
Pokaż odpowiedź
16 leży w [3, 6] — koniec przedziału też się liczy, bo w warunku jest <=.
Ć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 →

Porównywanie par: najpierw first, potem second

W części 1 widziałeś, że == sprawdza obie przegródki pary. Pary umieją jednak więcej: można zapytać, która z dwóch par jest mniejsza. To jedna z najważniejszych umiejętności pary — dzięki niej w części 7 posortujesz całą tablicę par jedną linijką. Dobra wiadomość: zasadę już znasz. Pary porównują się dokładnie tak jak słowa w słowniku, które porównywałeś w lekcji o napisach.

Najpierw first, a przy remisie second

Gdy porównujesz dwie pary, C++ najpierw patrzy na przegródki first. Jeśli są różne — ta para, której first jest mniejszy, jest mniejsza, i koniec: second w ogóle nie jest oglądany. Dopiero gdy first są równe, o wyniku decydują przegródki second. Dokładnie tak jak w słowniku: pierwsza litera rozstrzyga, a gdy jest taka sama — patrzymy na drugą.

porownania.cpp
pair<int, int> a = {1, 9}, b = {2, 0}, c = {1, 5}, d = {1, 9};
cout << (a < b) << "\n";    // first: 1 < 2 — to rozstrzyga
cout << (c < a) << "\n";    // first równe, więc second: 5 < 9
cout << (b < a) << "\n";    // first: 2 > 1 — b jest większa
cout << (a == d) << "\n";   // obie przegródki równe
cout << (a <= d) << "\n";   // równe, więc „mniejsza lub równa”
▶ Wyjście
1 1 0 1 1
porównaniefirstsecondwynik
(1, 9) < (2, 0)1 < 2nie patrzymyprawda
(1, 5) < (1, 9)1 = 15 < 9prawda
(2, 0) < (1, 9)2 > 1nie patrzymyfałsz
(1, 9) == (1, 9)1 = 19 = 9prawda

Zwróć uwagę na pierwszy wiersz: (1, 9) jest mniejsza od (2, 0), choć 9 jest dużo większe od 0. second liczy się tylko przy remisie na first.

Kolejność par = kolejność słownikowa Para (a, b) jest mniejsza od (c, d), gdy a < c, albo gdy a = c i b < d. Działają wszystkie znane operatory: <, >, <=, >=, ==, !=. Porównywać można tylko pary tego samego rodzaju — pair<int, int> z pair<int, int>, a nie z pair<string, int>.

Godziny porównują się same

Ta zasada ma piękne zastosowanie. Godzina zapisana jako para (godzina, minuta) porównuje się dokładnie tak, jak porównujemy godziny na zegarku: najpierw godziny, a przy tych samych godzinach — minuty. Nie trzeba nic przeliczać na minuty od północy!

godziny.cpp
pair<int, int> start = {9, 30}, koniec = {10, 5};
if (start < koniec) {
    cout << "start jest wczesniej\n";
}
pair<int, int> x = {9, 45};
cout << (x < start) << (x > start) << "\n";
▶ Wyjście
start jest wczesniej 01

9:30 jest przed 10:05, bo 9 < 10 — minuty nie mają znaczenia. 9:45 i 9:30 mają tę samą godzinę, więc decydują minuty: 45 > 30.

Tak samo działają daty w obrębie jednego roku zapisane jako (miesiąc, dzień): 15 marca, czyli (3, 15), jest przed 1 kwietnia, czyli (4, 1). Ważne tylko, żeby na pierwszym miejscu stała ważniejsza część: godzina przed minutą, miesiąc przed dniem.

Kolejność w parze ma znaczenie

Skoro pary porównują się najpierw po first, to o tym, co jest ważniejsze, decydujesz Ty — wybierając, co włożysz na pierwsze miejsce. Wyobraź sobie zawody: liczy się więcej punktów, a przy remisie — krótszy czas. Zawodnik A ma 90 punktów w 45 minut, zawodnik B — 90 punktów w 30 minut. Wygrywa B. Co powie porównanie par?

zla_kolejnosc.cpp
pair<int, int> a = {90, 45};   // (punkty, czas)
pair<int, int> b = {90, 30};
if (a > b) {
    cout << "wygrywa A\n";     // ŹLE: dłuższy czas „wygrał”
} else {
    cout << "wygrywa B\n";
}
▶ Wyjście — źle
wygrywa A

Punkty są równe, więc decyduje second — a 45 > 30. Para A wychodzi „większa”, choć A był wolniejszy. Problem w tym, że dla punktów lepiej jest więcej, a dla czasu — mniej. Para tego nie wie: obie przegródki porównuje tak samo, „więcej to więcej”.

Na szczęście jest prosty trik, który z tego wychodzi obronną ręką.

Sztuczka z minusem

Jeśli w jakiejś przegródce lepiej jest mniej, a w porównaniu chcesz, żeby lepsze było „większe” — zapisz tę wartość z minusem. Czas 30 to −30, a czas 45 to −45. Teraz −30 > −45, czyli krótszy czas daje większą parę. Para {punkty, -czas} jest tym większa, im zawodnik lepszy.

minus.cpp
int p1, t1, p2, t2;
cin >> p1 >> t1 >> p2 >> t2;
pair<int, int> a = {p1, -t1};   // więcej punktów i mniej czasu = lepiej
pair<int, int> b = {p2, -t2};
if (a > b) {
    cout << "pierwszy\n";
} else if (b > a) {
    cout << "drugi\n";
} else {
    cout << "remis\n";
}
▶ Wejście
90 45 90 30
▶ Wyjście
drugi
▶ Inne wejście
95 50 90 30
▶ Wyjście
pierwszy
▶ Jeszcze inne
80 20 80 20
▶ Wyjście
remis
chceszw parze zapisz
więcej punktów, przy remisie więcej bramek{punkty, bramki} i szukasz największej
więcej punktów, przy remisie mniej czasu{punkty, -czas} i szukasz największej
mniej czasu, przy remisie więcej punktów{czas, -punkty} i szukasz najmniejszej
więcej punktów, przy remisie imię alfabetycznie{-punkty, imie} i szukasz najmniejszej

Ostatni wiersz pokazuje, że minus działa też „w drugą stronę”: imion nie da się zapisać z minusem, więc to punkty dostają minus, a szukamy pary najmniejszej.

max i min działają na całych parach

Funkcje max i min z części 2 umieją porównywać wszystko, co da się porównać — także pary. max(a, b) zwraca większą z dwóch par według kolejności słownikowej, a min(a, b) — mniejszą. Zwracają całą parę, więc możesz od razu sięgnąć do jej przegródki.

max_min.cpp
pair<int, int> a = {3, 7}, b = {3, 9}, c = {2, 100};
pair<int, int> m = max(a, b);
cout << m.first << " " << m.second << "\n";
m = min(a, c);
cout << m.first << " " << m.second << "\n";
pair<string, int> x = {"Ola", 5}, y = {"Ala", 9};
cout << max(x, y).first << "\n";     // O jest dalej w alfabecie niż A
▶ Wyjście
3 9 2 100 Ola

(3, 7) i (3, 9) mają ten sam first, więc większa jest ta z większym second. (2, 100) jest mniejsza od (3, 7), bo 2 < 3 — setka nic tu nie zmienia.

Para pair<string, int> porównuje najpierw napisy — tak jak w lekcji o napisach: „Ola” > „Ala”, bo O jest dalej w alfabecie niż A. Liczba nie ma znaczenia, skoro napisy się różnią.

Porządkowanie trzech par

Skoro pary umieją się porównywać i zamieniać przez swap, możesz je uporządkować tym samym sposobem, którym w lekcji o if porządkowałeś trzy liczby, a w lekcji o napisach — trzy słowa: trzy porównania i trzy ewentualne zamiany.

trzy_pary.cpp
pair<int, int> a, b, c;
cin >> a.first >> a.second >> b.first >> b.second >> c.first >> c.second;
if (a > b) swap(a, b);
if (b > c) swap(b, c);    // największa trafia do c
if (a > b) swap(a, b);
cout << a.first << " " << a.second << "\n";
cout << b.first << " " << b.second << "\n";
cout << c.first << " " << c.second << "\n";
▶ Wejście
3 1 1 9 3 0
▶ Wyjście
1 9 3 0 3 1
krokabc
start(3, 1)(1, 9)(3, 0)
a > b — zamiana(1, 9)(3, 1)(3, 0)
b > c — zamiana(1, 9)(3, 0)(3, 1)
a > b — bez zmian(1, 9)(3, 0)(3, 1)

(3, 1) i (3, 0) mają ten sam first, więc o kolejności zdecydował second: najpierw (3, 0), potem (3, 1). Dla wielu par takie ręczne zamiany przestają wystarczać — w części 7 poznasz sort, który zrobi to za Ciebie.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
pair<int, int> a = {2, 1}, b = {1, 9};
cout << (a < b);
Pokaż odpowiedź
0first: 2 > 1 — to rozstrzyga. Para a jest większa, więc a < b to fałsz.
Co wypisze ten fragment?
pair<int, int> a = {4, 3}, b = {4, 8};
cout << (a < b) << (a == b);
Pokaż odpowiedź
10first równe (4 = 4), więc decyduje second: 3 < 8. Pary nie są równe.
Co wypisze ten fragment?
pair<int, int> a = {5, 5};
cout << (a <= a) << (a < a);
Pokaż odpowiedź
10Para jest równa samej sobie, więc „mniejsza lub równa” — tak, ale „mniejsza” — nie.
Para z napisem. Co wypisze ten fragment?
pair<string, int> a = {"kot", 1}, b = {"kotek", 0};
cout << (a < b);
Pokaż odpowiedź
1Napisy się różnią, więc decydują one: „kot” to początek słowa „kotek”, a krótszy napis jest mniejszy. Liczby nie mają znaczenia.
Co wypisze ten fragment?
pair<int, int> p = max(make_pair(1, 50), make_pair(2, 0));
cout << p.second;
Pokaż odpowiedź
0(2, 0) jest większa od (1, 50), bo 2 > 1. Jej second to 0.
Sztuczka z minusem. Co wypisze ten fragment?
pair<int, int> a = {7, -10}, b = {7, -12};
cout << (a > b);
Pokaż odpowiedź
1first równe, a −10 > −12. Gdy second to „minus czas”, wygrywa krótszy czas — 10 minut zamiast 12.
Godziny. Co wypisze ten fragment?
pair<int, int> t1 = {12, 59}, t2 = {13, 0};
cout << (t1 < t2);
Pokaż odpowiedź
112:59 jest przed 13:00 — rozstrzyga godzina (12 < 13), choć 59 minut to dużo więcej niż 0.
Co wypisze ten fragment?
pair<int, int> a = {3, 4}, b = {3, 4};
cout << (a < b) << (a > b) << (a == b);
Pokaż odpowiedź
001Pary są równe: ani mniejsza, ani większa.
Ć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 Która godzina wcześniej?łatwe✓ zaliczone Godziny jako pary porównują się same. Wypisz wcześniejszą z dwóch. pary porównane <godzina (h, m)HH:MM Rozwiąż 3.2 Porównaj paryłatwe✓ zaliczone Mniejsza, większa czy równa? Pary porównuje się najpierw po first, a przy remisie po second. <, >, ==kolejność słownikowafirst, potem second Rozwiąż 3.3 Lepszy wynikłatwe✓ zaliczone Więcej punktów wygrywa, a przy remisie — krótszy czas. Sztuczka z minusem w praktyce. {punkty, -czas}sztuczka z minusemporównanie par Rozwiąż 3.4 Pierwszy i ostatni na meciełatwe✓ zaliczone Godziny dobiegnięcia na metę jako pary. Kto pierwszy, kto ostatni? min i max na parach. min i max pargodzina (h, m)rekordy Rozwiąż 3.5 Trzy pary po koleiłatwe✓ zaliczone Ułóż trzy pary rosnąco trzema porównaniami i zamianami. swap partrzy porównaniakolejność słownikowa Rozwiąż 3.6 Najlepszy uczeńśrednie✓ zaliczone Najwięcej punktów wygrywa, a przy remisie — imię wcześniejsze w alfabecie. Para {-punkty, imię}. {-punkty, imie}najmniejsza parapair<int, string> Rozwiąż 3.7 Konkurs skokówśrednie✓ zaliczone Najdłuższy skok wygrywa, przy remisie — wyższe noty, a potem wcześniejszy numer startowy. {odległość, noty}ostro większanumer zwycięzcy Rozwiąż 3.8 Czy pary rosną?łatwe✓ zaliczone Sprawdź, czy każda kolejna para jest ostro większa od poprzedniej. poprzednia parap <= poprzedniapierwszy błąd Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Tablica par: rząd par zamiast dwóch tablic

Pojedyncza para przydaje się rzadko. Prawdziwa siła pojawia się, gdy par jest dużo: lista uczniów z punktami, lista punktów na mapie, lista produktów z cenami. Wtedy robisz tablicę par — dokładnie taką tablicę jak w lekcji o tablicach, tylko w każdym pudełku leży cała para. To jest właśnie rozwiązanie problemu z początku lekcji: zamiast dwóch równoległych tablic masz jedną, w której dane każdej osoby trzymają się razem.

Rząd par i dwa poziomy dostępu

pair<int, int> t[4]; to cztery pudełka, a w każdym para. t[2] to cała para z pudełka 2, a t[2].first — jej pierwsza przegródka. Czytaj od lewej: „z tablicy t weź pudełko 2, a z niego przegródkę first”. To ten sam pomysł co t[i][j] z tablicy napisów w lekcji o napisach.

pair<int, int> t[4] = {{3, 7}, {1, 2}, {5, 0}, {4, 4}}; — t[2] (niebieskie pudełko) to para (5, 0): t[2].first = 5, a t[2].second = 0.
tablica_par.cpp
pair<int, int> t[4] = {{3, 7}, {1, 2}, {5, 0}, {4, 4}};
cout << t[0].first << " " << t[0].second << "\n";
cout << t[2].first << "\n";       // first z pudełka 2
t[1].second = 9;                  // zmieniamy jedną przegródkę
cout << t[1].first << " " << t[1].second << "\n";
pair<int, int> p = t[3];          // kopia całej pary z pudełka 3
cout << p.first + p.second << "\n";
▶ Wyjście
3 7 5 1 9 8

Przy tworzeniu tablicy par możesz podać wartości w klamrach — każda para we własnych klamrach, wszystkie razem w klamrach tablicy. Dlatego zaczyna się od dwóch klamer: {{3, 7}, …}.

Dobra wiadomość: tablica par utworzona bez wartości — nawet w środku main — ma w każdym pudełku parę z zerami, bo każda nowa para startuje od zer. Śmieci, które pamiętasz z int t[5];, tu się nie pojawią.

Wczytywanie n par

Tablicę par wczytujesz pętlą, tak jak zwykłą tablicę — tylko w każdym obrocie wczytujesz dwie przegródki. Rozmiar bierzesz z ograniczeń zadania, z małym zapasem.

wczytaj_pary.cpp
pair<int, int> t[1005];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i].first >> t[i].second;
}
for (int i = n - 1; i >= 0; i--) {         // od końca
    cout << t[i].first << " " << t[i].second << "\n";
}
▶ Wejście
3 1 2 3 4 5 6
▶ Wyjście
5 6 3 4 1 2
powyzej_sredniej.cpp
pair<string, int> u[1005];        // (imię, punkty)
int n;
cin >> n;
int suma = 0;
for (int i = 0; i < n; i++) {
    cin >> u[i].first >> u[i].second;
    suma += u[i].second;
}
for (int i = 0; i < n; i++) {
    if (u[i].second * n > suma) { // powyżej średniej, bez ułamków
        cout << u[i].first << "\n";
    }
}
▶ Wejście
4 Ola 90 Jan 60 Ewa 85 Igor 50
▶ Wyjście
Ola Ewa

Prawy program to zadanie, od którego zaczynała się lekcja o tablicach — „wypisz tych, którzy mają więcej niż średnia” — tylko teraz razem z imionami. Średnia to 285 / 4 = 71,25. Zamiast liczyć ją na ułamkach, porównujemy punkty · n z sumą: punkty > suma / n to to samo co punkty · n > suma, a działa na samych liczbach całkowitych.

Szukanie po first: tablica-ściąga par

Tablica par świetnie nadaje się na ściągę „klucz → wartość”: w first nazwa, w second to, co o niej wiemy. Żeby coś znaleźć, idziesz po tablicy i porównujesz first z szukanym kluczem — jak w szukaniu w zwykłej tablicy.

cennik.cpp
pair<string, int> cennik[4] = {{"chleb", 450}, {"mleko", 389},
                               {"maslo", 799}, {"jajka", 120}};
string co;
cin >> co;
int cena = -1;                       // -1 znaczy „nie ma”
for (int i = 0; i < 4; i++) {
    if (cennik[i].first == co) {
        cena = cennik[i].second;
        break;
    }
}
if (cena == -1) {
    cout << "nie ma\n";
} else {
    cout << cena / 100 << "." << cena % 100 << " zl\n";
}
▶ Wejście
mleko
▶ Wyjście
3.89 zl
▶ Inne wejście
ser
▶ Wyjście
nie ma

Ceny trzymamy w groszach — jako liczby całkowite — i dopiero przy wypisywaniu dzielimy je na złote i grosze. To nawyk z lekcji o modulo: pieniądze w groszach nie mają problemów z dokładnością liczb z przecinkiem.

Uważaj na grosze mniejsze od 10: 405 groszy to 4 zł i 5 gr, a ten program wypisałby „4.5”. W ćwiczeniu z cennikiem dopisz w takim przypadku zero przed groszami.

Para (wartość, pozycja): najmniejsza i gdzie stoi

Teraz sztuczka, która łączy tablice z porównywaniem par. Często trzeba znaleźć najmniejszą liczbę i jej pozycję. W lekcji o tablicach pamiętałeś dwie zmienne. Z parą wystarczy jedna: każdą liczbę zamieniasz w parę (wartość, numer) i szukasz najmniejszej pary. Bonus za darmo: przy remisie wartości o kolejności decyduje numer, więc wygrywa pierwsze wystąpienie.

wartosc_pozycja.cpp
int n;
cin >> n;
pair<int, int> najm = {2000000000, 0};   // na start „nieskończoność”
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    najm = min(najm, make_pair(x, i));   // (wartość, numer)
}
cout << najm.first << " " << najm.second << "\n";
▶ Wejście
6 5 3 8 3 9 4
▶ Wyjście
3 2
Pary (wartość, numer). Najmniejsza wartość to 3 — dwa razy. (3, 2) < (3, 4), bo przy remisie decyduje numer: wygrywa pierwsze wystąpienie (niebieskie).

Na start bierzemy parę z ogromną wartością, żeby pierwsza liczba na pewno ją pobiła. Możesz też — jak w lekcji o tablicach — zacząć od pierwszej liczby.

A gdyby przy remisie miało wygrać ostatnie wystąpienie? Szukaj największej pary (wartość, numer) przez max — przy remisie wygra większy numer. Albo użyj sztuczki z minusem z części 3.

Każda para z każdą

W lekcji o tablicach porównywałeś każdy element z każdym dwiema pętlami: i od 0, a j od i + 1. Z tablicą par robisz dokładnie to samo. Przykład: ile par punktów leży na jednej poziomej linii, czyli ma ten sam y?

ta_sama_linia.cpp
pair<int, int> p[1005];          // (x, y)
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
}
int ile = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (p[i].second == p[j].second) ile++;
    }
}
cout << ile << "\n";
▶ Wejście
4 1 5 3 5 2 7 9 5
▶ Wyjście
3

Punkty z y = 5 to numery 0, 1 i 3. Tworzą trzy pary: (0, 1), (0, 3) i (1, 3). Punkt (2, 7) nie ma towarzystwa.

Pamiętaj o koszcie: n punktów to około n² / 2 porównań. Dla tysiąca punktów to pół miliona — błyskawicznie. Dla stu tysięcy — pięć miliardów, za dużo. W części 8 zobaczysz, jak sortowanie par pomaga w takich zadaniach.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
pair<int, int> t[3] = {{1, 2}, {3, 4}, {5, 6}};
cout << t[1].second + t[2].first;
Pokaż odpowiedź
9t[1].second to 4, t[2].first to 5. Razem 9.
Co wypisze ten fragment?
pair<int, int> t[3] = {{1, 2}, {3, 4}, {5, 6}};
swap(t[0], t[2]);
cout << t[0].first << t[2].second;
Pokaż odpowiedź
52Całe pary zamieniają się miejscami: t[0] to teraz (5, 6), a t[2] — (1, 2).
Najmniejsza para. Co wypisze ten fragment?
pair<int, int> t[4] = {{2, 9}, {2, 1}, {1, 5}, {2, 3}};
pair<int, int> m = t[0];
for (int i = 1; i < 4; i++) {
    if (t[i] < m) m = t[i];
}
cout << m.first << m.second;
Pokaż odpowiedź
15Najmniejszy first to 1 — ma go tylko para (1, 5). second się nie liczy, bo first rozstrzyga.
Tablica par bez wartości. Co wypisze ten fragment?
pair<int, int> t[3];
cout << t[2].first + t[1].second;
Pokaż odpowiedź
0Każda nowa para ma zera — także w tablicy utworzonej w środku main.
Co wypisze ten fragment?
pair<string, int> u[2] = {{"Ola", 5}, {"Jan", 7}};
cout << u[1].first[0] << u[0].second;
Pokaż odpowiedź
J5u[1].first to napis „Jan”, a jego znak 0 to J. u[0].second to 5.
Para (wartość, pozycja). Co wypisze ten fragment?
int a[3] = {7, 2, 2};
pair<int, int> m = {100, 0};
for (int i = 0; i < 3; i++) {
    m = min(m, make_pair(a[i], i));
}
cout << m.second;
Pokaż odpowiedź
1Pary to (7, 0), (2, 1) i (2, 2). Najmniejsza jest (2, 1) — przy remisie wartości wygrywa mniejszy numer.
Co wypisze ten fragment?
pair<int, int> t[3] = {{1, 1}, {2, 2}, {3, 3}};
for (int i = 0; i < 3; i++) {
    t[i].first *= 2;
}
cout << t[2].first << t[2].second;
Pokaż odpowiedź
63Podwajamy tylko przegródki first: t[2] to teraz (6, 3).
Ile par jest równych?
pair<int, int> t[3] = {{4, 1}, {4, 1}, {2, 8}};
int k = 0;
for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 3; j++)
        if (t[i] == t[j]) k++;
cout << k;
Pokaż odpowiedź
1Tylko t[0] i t[1] są równe: (4, 1) i (4, 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 Pary od końcałatwe✓ zaliczone Wczytaj n par do tablicy i wypisz je od ostatniej do pierwszej w postaci (a, b). pair<int, int> t[1005]pętla od końcaformat (a, b) Rozwiąż 4.2 Kto ma najwięcej punktów?łatwe✓ zaliczone Tablica par (imię, punkty): znajdź osobę z największą liczbą punktów. pair<string, int>rekordpierwszy przy remisie Rozwiąż 4.3 Cennikłatwe✓ zaliczone Tablica par (towar, cena w groszach) jako ściąga. Odpowiedz na pytania o ceny. tablica-ściągaszukanie po firstzłote i grosze Rozwiąż 4.4 Najmniejsza i największa z miejscemłatwe✓ zaliczone Pary (wartość, numer): min daje pierwsze wystąpienie najmniejszej, max — ostatnie największej. para (wartość, numer)min i max parremisy Rozwiąż 4.5 Najbliższy punktśrednie✓ zaliczone Dla każdego pytania znajdź najbliższy punkt z listy. Para (odległość, numer) sama rozstrzyga remisy. tablica punktówpara (odległość, numer)abs Rozwiąż 4.6 Najbliższa para punktówśrednie✓ zaliczone Każdy punkt z każdym: która para punktów leży najbliżej siebie? każdy z każdymj od i + 1abs Rozwiąż 4.7 Zamiany w tablicy parłatwe✓ zaliczone Wykonaj na tablicy par serię zamian swap(t[i], t[j]) — całe pary jadą razem. swap(t[i], t[j])numeracja od 1tablica par Rozwiąż 4.8 Suma punktów każdej osobyśrednie✓ zaliczone Imiona się powtarzają. Zsumuj punkty każdej osoby w tablicy par (imię, suma). tablica par jako słownikszukaj, a jak nie ma — dopiszpair<string, int> Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Rozpakowywanie i pary w parach

Ciągłe pisanie u[i].first i u[i].second szybko robi się męczące — a po kilku linijkach trudno pamiętać, która przegródka to imię, a która punkty. W tej części poznasz dwie rzeczy. Pierwsza to rozpakowywanie: nadajesz przegródkom pary własne, czytelne nazwy. Druga to para w parze: gdy wartości są trzy, druga przegródka sama może być parą — i wtedy trzy wartości porównują się naraz, we właściwej kolejności.

auto [a, b] — nazwy zamiast first i second

Zapis auto [imie, punkty] = u; tworzy dwie nowe zmienne i wkłada do nich przegródki pary: do pierwszej first, do drugiej second. Słowo auto znasz z lekcji o typach — kompilator sam odgadnie, że imie to string, a punkty to int. Nawiasy są kwadratowe.

rozpakuj.cpp
pair<string, int> u = {"Ola", 95};
auto [imie, punkty] = u;      // imie = "Ola", punkty = 95
cout << imie << " ma " << punkty << " pkt\n";
punkty = 100;                 // zmieniamy kopię…
cout << u.second << "\n";     // …a para zostaje bez zmian
▶ Wyjście
Ola ma 95 pkt 95

Zmienne imie i punkty to kopie przegródek. Zmiana punkty nie zmienia pary u — dokładnie tak jak w pętli for (char c : s) bez znaku &.

Rozpakowywanie wymaga C++17. Sprawdzarka i każdy nowy kompilator go mają. Jeśli Twój edytor zgłasza błąd przy nawiasach kwadratowych, poszukaj w jego ustawieniach opcji standardu C++ i wybierz C++17 (albo nowszy).

auto &[a, b] — zmiany trafiają do pary

Gdy chcesz przez nowe nazwy zmieniać parę, dopisz & — tak samo jak w for (char &c : s). Wtedy x i y nie są kopiami, tylko drugimi nazwami przegródek: co zrobisz z x, dzieje się z p.first.

rozpakuj_ref.cpp
pair<int, int> p = {3, 8};
auto &[x, y] = p;     // x to p.first, y to p.second
x += 10;              // p.first = 13
swap(x, y);           // zamieniamy przegródki p
cout << p.first << " " << p.second << "\n";
▶ Wyjście
8 13
Bez & — kopia, z & — oryginał auto [a, b] = p; — dwie nowe zmienne z kopiami wartości; zmiany nie wracają do p. auto &[a, b] = p; — dwie nowe nazwy dla przegródek p; każda zmiana zmienia p. Ta sama zasada co w pętli „dla każdego znaku” z lekcji o pętli for.

Rozpakowywanie w pętli

Najwięcej daje rozpakowywanie w pętli po tablicy par. Pętla „dla każdego” — for (auto [imie, punkty] : u) — czyta się prawie jak zdanie: „dla każdej pary z tablicy u nazwij jej przegródki imie i punkty”. Uwaga jednak: taka pętla przechodzi przez wszystkie pudełka tablicy. Gdy tablica ma zapas (t[1005], a par jest tylko n), użyj zwykłej pętli z indeksem i rozpakuj parę w środku.

petla_rozpakuj.cpp
pair<string, int> u[3] = {{"Ola", 95}, {"Jan", 87}, {"Ewa", 91}};
for (auto [imie, punkty] : u) {        // po wszystkich 3 pudełkach
    cout << imie << ": " << punkty << "\n";
}
for (auto &[imie, punkty] : u) {       // z & — zmieniamy tablicę
    punkty += 5;
}
cout << u[1].second << "\n";
▶ Wyjście
Ola: 95 Jan: 87 Ewa: 91 92
petla_n.cpp
pair<int, int> t[1005];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i].first >> t[i].second;
}
for (int i = 0; i < n; i++) {          // tylko n pierwszych pudełek
    auto [szer, wys] = t[i];
    cout << szer * wys << "\n";
}
▶ Wejście
2 3 4 5 6
▶ Wyjście
12 30

W prawym programie nazwy szer i wys od razu mówią, co oznaczają liczby: to prostokąty, a wynik to ich pola. Porównaj z t[i].first * t[i].second — działa tak samo, ale trzeba się domyślać.

Para w parze: trzy wartości

Co, gdy wartości są trzy — na przykład data: rok, miesiąc i dzień? Para ma tylko dwie przegródki… ale druga przegródka może sama być parą! pair<int, pair<int, int>> d; to para, której first to liczba, a second — kolejna para. Do dnia dostajesz się dwoma krokami: d.second.second — „z d weź second, a z niego jeszcze raz second”.

pair<int, pair<int, int>> d = {2026, {11, 8}}; — first to rok 2026, a second to cała para (miesiąc, dzień): d.second.first = 11, d.second.second = 8.
daty.cpp
pair<int, pair<int, int>> a = {2026, {11, 8}};   // (rok, (miesiąc, dzień))
pair<int, pair<int, int>> b = {2025, {12, 24}};
cout << a.second.second << "." << a.second.first << "." << a.first << "\n";
if (b < a) {
    cout << "b jest wczesniej\n";
}
int d, m, r;
cin >> d >> m >> r;
pair<int, pair<int, int>> c = {r, {m, d}};       // kolejność: rok, miesiąc, dzień
cout << (c < a) << "\n";
▶ Wejście
31 12 2026
▶ Wyjście
8.11.2026 b jest wczesniej 0

Najważniejsze: daty porównują się chronologicznie. Porównanie par zaczyna od first, czyli roku; przy tym samym roku przechodzi do second — pary (miesiąc, dzień) — i tam znowu najpierw miesiąc, potem dzień. Dokładnie tak porównujemy daty w kalendarzu.

Dlatego przy wczytywaniu ustawiamy części od najważniejszej: dane przychodzą jako dzień, miesiąc, rok, a w parze stoją jako rok, (miesiąc, dzień). 31 grudnia 2026 nie jest wcześniej niż 8 listopada 2026 — stąd 0.

Trzy kryteria naraz: tabela medalowa

Para w parze to gotowe porównanie według trzech kryteriów. Klasyczny przykład to tabela medalowa igrzysk: wygrywa kraj z największą liczbą złotych medali, przy remisie — z większą liczbą srebrnych, a potem brązowych. Para {złote, {srebrne, brązowe}} porównuje się dokładnie w tej kolejności.

medale.cpp
int n;
cin >> n;
pair<int, pair<int, int>> najlepszy = {-1, {0, 0}};
int ktory = 0;
for (int i = 1; i <= n; i++) {
    int z, s, b;
    cin >> z >> s >> b;
    pair<int, pair<int, int>> m = {z, {s, b}};
    if (m > najlepszy) {           // ostro większy: przy remisie zostaje wcześniejszy
        najlepszy = m;
        ktory = i;
    }
}
cout << ktory << "\n";
▶ Wejście
3 2 5 1 3 0 0 2 7 0
▶ Wyjście
2

Kraj 2 ma tylko trzy złote medale i nic więcej, ale trzy złote to więcej niż dwa — srebra i brązy kraju 1 i 3 nic tu nie zmieniają. Gdyby dwa kraje miały tyle samo złotych, zdecydowałyby srebrne.

Start od {-1, {0, 0}} gwarantuje, że pierwszy kraj zawsze pobije rekord — nawet gdy nie ma żadnych medali.

Kiedy para to już za mało Para w parze dobrze sprawdza się dla trzech wartości, które porównujesz w ustalonej kolejności. Przy czterech i więcej wartościach zapis p.second.second.first robi się nieczytelny. Wtedy lepsza jest struktura (struct), w której każde pole ma własną nazwę — poznasz ją w jednej z dalszych lekcji. Do tego czasu pomagają rozpakowywanie i komentarze.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
pair<int, int> p = {5, 2};
auto [a, b] = p;
a++;
cout << a << p.first;
Pokaż odpowiedź
65a to kopia — zwiększa się tylko ona. p.first zostaje 5.
A z &?
pair<int, int> p = {5, 2};
auto &[a, b] = p;
a++;
cout << p.first << b;
Pokaż odpowiedź
62Z & zmienna a to druga nazwa p.first, więc p.first zmienia się na 6.
Para w parze. Co wypisze ten fragment?
pair<int, pair<int, int>> q = {1, {2, 3}};
cout << q.second.first + q.first;
Pokaż odpowiedź
3q.second to para (2, 3), jej first to 2. Plus q.first (1) daje 3.
Co wypisze ten fragment?
pair<int, pair<int, int>> a = {1, {5, 0}}, b = {1, {4, 9}};
cout << (a < b);
Pokaż odpowiedź
0first równe (1). Porównujemy second: (5, 0) i (4, 9) — 5 > 4, więc a jest większa.
Co wypisze ten fragment?
pair<int, int> t[2] = {{1, 2}, {3, 4}};
int s = 0;
for (auto [x, y] : t) s += x * y;
cout << s;
Pokaż odpowiedź
141 · 2 + 3 · 4 = 2 + 12 = 14.
Pętla bez &. Co wypisze ten fragment?
pair<int, int> t[2] = {{1, 2}, {3, 4}};
for (auto [x, y] : t) x = 0;
cout << t[0].first;
Pokaż odpowiedź
1Bez & zerujemy kopie, a tablica zostaje bez zmian.
Pętla z &. Co wypisze ten fragment?
pair<int, int> t[2] = {{1, 2}, {3, 4}};
for (auto &[x, y] : t) swap(x, y);
cout << t[1].first << t[1].second;
Pokaż odpowiedź
43Z & zamieniamy prawdziwe przegródki: t[1] to teraz (4, 3).
Co wypisze ten fragment?
pair<int, pair<int, int>> d = {2024, {2, 29}};
cout << d.second.second << "/" << d.second.first;
Pokaż odpowiedź
29/2d.second to (2, 29): miesiąc 2 i dzień 29.
Ć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 Najwcześniejsza i najpóźniejsza datałatwe✓ zaliczone Daty jako pary (rok, (miesiąc, dzień)) porównują się chronologicznie. Znajdź skrajne. pair<int, pair<int, int>>min i maxDD.MM.RRRR Rozwiąż 5.2 Tabela ligowaśrednie✓ zaliczone Mistrz ligi: najwięcej punktów, potem lepszy bilans bramek, potem więcej strzelonych. para w parze{pkt, {bilans, gole}}ostro większa Rozwiąż 5.3 Odwróć wszystkie paryłatwe✓ zaliczone Zamień przegródki w każdej parze pętlą for (auto &[a, b] : …) i znajdź największą parę. auto &[a, b]swapmax par Rozwiąż 5.4 Największy prostokątłatwe✓ zaliczone Prostokąty jako pary (szerokość, wysokość). Który ma największe pole? auto [szer, wys]long longpierwszy przy remisie Rozwiąż 5.5 Najszybsze okrążeniełatwe✓ zaliczone Czasy okrążeń (minuty, sekundy, setne) jako para w parze. Które okrążenie było najszybsze? pair<int, pair<int, int>>minM:SS.CC Rozwiąż 5.6 Kto jest najstarszy?średnie✓ zaliczone Najstarszy to ten z najwcześniejszą datą urodzenia. Daty jako (rok, (miesiąc, dzień)). data jako para w parzenajwcześniejszaimię osobno Rozwiąż 5.7 Przesuń wszystkie punktyłatwe✓ zaliczone Przesuń każdy punkt z tablicy o ten sam wektor — rozpakowując go z &. auto &[x, y]tablica punktówzmiana w miejscu Rozwiąż 5.8 Najdalej od środkaśrednie✓ zaliczone Najdalszy punkt od (0, 0), a przy remisie — mniejszy w porządku par. Klucz {odległość², {−x, −y}}. para w parzelong longsztuczka z minusem Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Pary na planszy: kierunki i ruchy

W lekcji o tablicach poznałeś plansze: tablice dwuwymiarowe i napisy ułożone w wiersze, po których chodziłeś, sprawdzając sąsiednie kratki. Kratkę na planszy opisują dwie liczby — numer wiersza i numer kolumny — więc to idealne miejsce dla par. W tej części para będzie dwiema rzeczami naraz: pozycją (wiersz, kolumna) i krokiem, czyli o ile zmienia się wiersz i kolumna przy jednym ruchu. Dzięki temu ruchy w czterech, a nawet ośmiu kierunkach zapiszesz jedną pętlą zamiast łańcucha if-ów.

Kierunki jako pary

Ustalmy, jak jest numerowana plansza: wiersze od góry (wiersz 0 to górny), kolumny od lewej. Krok w górę zmniejsza numer wiersza o 1, a kolumny nie zmienia — to para (−1, 0). Krok w prawo nie zmienia wiersza i zwiększa kolumnę — (0, 1). Cztery kierunki to cztery pary, które wygodnie trzymać w tablicy:

kierunki.cpp
//                         góra      prawo    dół      lewo
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string kierunki = "GPDL";   // litera kierunku na tej samej pozycji
literakieruneknumerkrok (dw, dk)
Ggóra0(-1, 0)
Pprawo1(0, 1)
Ddół2(1, 0)
Llewo3(0, -1)
Robot ● stoi w kratce (1, 1). Sąsiad w górę to (1 − 1, 1) = (0, 1), w prawo (1, 1 + 1) = (1, 2) — do pozycji dodajemy krok z tabelki.

Kolejność kierunków nie jest przypadkowa: góra, prawo, dół, lewo — zgodnie z ruchem wskazówek zegara. Za chwilę zobaczysz, że dzięki temu obrót w prawo to po prostu „następny numer”.

Literę zamienisz na numer kierunku przez kierunki.find(c) — trik z lekcji o napisach. Litera G jest na pozycji 0, więc to kierunek 0.

Robot wykonuje polecenia

Robot stoi w kratce (0, 0) na bardzo dużej planszy i dostaje napis z poleceniami — literami G, P, D i L. Gdzie skończy? Dla każdej litery bierzemy jej krok z tablicy i dodajemy do pozycji: wiersz do wiersza, kolumnę do kolumny.

robot.cpp
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string kierunki = "GPDL";
string polecenia;
cin >> polecenia;
pair<int, int> poz = {0, 0};             // (wiersz, kolumna)
for (char c : polecenia) {
    int k = kierunki.find(c);            // numer kierunku
    poz.first += ruch[k].first;
    poz.second += ruch[k].second;
}
cout << poz.first << " " << poz.second << "\n";
▶ Wejście
PPGGLD
▶ Wyjście
-1 1
poleceniekrokpozycja
start—(0, 0)
P(0, 1)(0, 1)
P(0, 1)(0, 2)
G(−1, 0)(−1, 2)
G(−1, 0)(−2, 2)
L(0, −1)(−2, 1)
D(1, 0)(−1, 1)

Bez tablicy kroków potrzebowałbyś czterech if-ów — po jednym na każdą literę. Z tablicą cały ruch to dwie linijki, takie same dla każdego kierunku.

Plansza ze ścianami i brzegami

Prawdziwa plansza ma brzegi, a na niej stoją ściany #. Robot, który miałby wejść w ścianę albo wyjść poza planszę, zostaje na miejscu. Schemat znasz z lekcji o tablicach: najpierw liczysz nową pozycję, potem sprawdzasz, czy leży na planszy i czy jest wolna — i dopiero wtedy się przesuwasz.

Plansza 3 × 4 ze ścianą w kratce (1, 1). Robot startuje w (0, 0) (niebieska) i po poleceniach PDPPDDP kończy w (2, 3) (zielona).
robot_plansza.cpp
int n, m;
cin >> n >> m;
string p[100];
for (int i = 0; i < n; i++) {
    cin >> p[i];
}
string polecenia;
cin >> polecenia;
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string kierunki = "GPDL";
pair<int, int> poz = {0, 0};
for (char c : polecenia) {
    int k = kierunki.find(c);
    int nw = poz.first + ruch[k].first;      // nowa pozycja…
    int nk = poz.second + ruch[k].second;
    if (nw >= 0 && nw < n && nk >= 0 && nk < m && p[nw][nk] != '#') {
        poz = {nw, nk};                      // …tylko jeśli wolna
    }
}
cout << poz.first << " " << poz.second << "\n";
▶ Wejście
3 4 .... .#.. .... PDPPDDP
▶ Wyjście
2 3

Prześledź polecenia: P — do (0, 1). D — w kratce (1, 1) stoi ściana, robot zostaje. P, P — do (0, 3). D, D — do (2, 3). Ostatnie P wyprowadziłoby robota poza planszę (kolumna 4 nie istnieje), więc zostaje w (2, 3).

Kolejność warunków znów jest ważna: najpierw brzegi, a dopiero na końcu p[nw][nk]. Odwrotnie program zajrzałby poza planszę — skrócone obliczanie z lekcji o if chroni nas, tylko gdy sprawdzenie brzegów stoi pierwsze.

Sąsiedzi kratki jedną pętlą

Ta sama tablica kroków przydaje się nie tylko do chodzenia, ale też do oglądania sąsiadów. Zamiast czterech prawie identycznych if-ów piszesz jedną pętlę po kierunkach. Przykład: ile ścian otacza kratkę (w, k)?

sasiedzi.cpp
int n, m;
cin >> n >> m;
string p[100];
for (int i = 0; i < n; i++) cin >> p[i];
int w, k;
cin >> w >> k;
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int sciany = 0;
for (auto [dw, dk] : ruch) {          // dla każdego kroku
    int nw = w + dw, nk = k + dk;
    if (nw >= 0 && nw < n && nk >= 0 && nk < m && p[nw][nk] == '#') {
        sciany++;
    }
}
cout << sciany << "\n";
▶ Wejście
3 3 .#. ##. .#. 1 1
▶ Wyjście
3

Tu przydaje się rozpakowywanie z części 5: for (auto [dw, dk] : ruch) przechodzi po wszystkich czterech krokach i od razu nazywa ich przegródki. Tablica ruch ma dokładnie 4 pudełka, więc pętla „dla każdego” jest tu bezpieczna.

Kratka (1, 1) ma ścianę w górę, w lewo i w dół — w prawo jest wolne pole. Wynik: 3.

Osiem kierunków i skoczek szachowy

Kierunków może być więcej. Osiem sąsiadów — razem z ukośnymi — to wszystkie kroki (dw, dk), w których dw i dk są z {−1, 0, 1}, oprócz (0, 0). A skoczek szachowy skacze „w literę L”: dwa pola w jedną stronę i jedno w bok. Takich skoków jest osiem — i znowu wystarczy tablica par.

skoczek.cpp
pair<int, int> skok[8] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
                          {1, -2}, {1, 2}, {2, -1}, {2, 1}};
int w, k;
cin >> w >> k;                  // pole na szachownicy 8 × 8, od 0 do 7
int ile = 0;
for (auto [dw, dk] : skok) {
    int nw = w + dw, nk = k + dk;
    if (nw >= 0 && nw < 8 && nk >= 0 && nk < 8) ile++;
}
cout << ile << "\n";
▶ Wejście
0 0
▶ Wyjście
2
▶ Inne wejście
3 3
▶ Wyjście
8
Skoczek ♞ i osiem pól, na które może skoczyć (zielone). W rogu szachownicy większość skoków wypada poza planszę — zostają tylko 2.

Obrót w prawo to następny numer

Ostatni pomysł tej części. Robot ma kierunek, w którym patrzy, zapisany jako numer: 0 — góra, 1 — prawo, 2 — dół, 3 — lewo. Polecenie F to krok do przodu, R — obrót w prawo, L — obrót w lewo. Obrót w prawo to następny kierunek zgodnie z ruchem zegara: numer + 1, a po lewie (3) wracamy do góry (0) — to reszta z dzielenia przez 4 z lekcji o modulo. Obrót w lewo to cofnięcie o jeden, które bez liczb ujemnych zapiszesz jako + 3.

obroty.cpp
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string polecenia;
cin >> polecenia;
pair<int, int> poz = {0, 0};
int d = 0;                              // patrzymy w górę
for (char c : polecenia) {
    if (c == 'R') {
        d = (d + 1) % 4;                // obrót w prawo
    } else if (c == 'L') {
        d = (d + 3) % 4;                // obrót w lewo
    } else {                            // F — krok do przodu
        poz.first += ruch[d].first;
        poz.second += ruch[d].second;
    }
}
cout << poz.first << " " << poz.second << " " << d << "\n";
▶ Wejście
FFRFFRF
▶ Wyjście
-1 2 2

Robot idzie dwa kroki w górę do (−2, 0), obraca się w prawo, idzie dwa kroki w prawo do (−2, 2), znowu obraca się w prawo — patrzy teraz w dół — i robi krok do (−1, 2). Na końcu patrzy w kierunku 2, czyli w dół.

Dlaczego (d + 3) % 4, a nie (d - 1) % 4? Dla d = 0 wyszłoby (−1) % 4 = −1 — a pamiętasz z lekcji o modulo, że w C++ reszta z liczby ujemnej jest ujemna. Dodanie 3 to ten sam obrót (trzy razy w prawo = raz w lewo), ale bez minusów.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
pair<int, int> p = {2, 2};
p.first += ruch[3].first;
p.second += ruch[3].second;
cout << p.first << p.second;
Pokaż odpowiedź
21ruch[3] to krok w lewo (0, −1): wiersz się nie zmienia, kolumna maleje do 1.
Co wypisze ten fragment?
string kierunki = "GPDL";
cout << kierunki.find('D');
Pokaż odpowiedź
2Litera D stoi w napisie „GPDL” na pozycji 2 — to numer kierunku „dół”.
Dwa obroty w lewo. Co wypisze ten fragment?
int d = 0;
d = (d + 3) % 4;
d = (d + 3) % 4;
cout << d;
Pokaż odpowiedź
2Z góry (0) w lewo to lewo (3), a z lewa w lewo to dół (2). Dwa obroty w lewo to odwrócenie się tyłem.
Gdzie skończy robot?
pair<int, int> ruch[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
string kierunki = "GPDL", s = "PPDL";
pair<int, int> p = {0, 0};
for (char c : s) {
    int k = kierunki.find(c);
    p.first += ruch[k].first;
    p.second += ruch[k].second;
}
cout << p.first << " " << p.second;
Pokaż odpowiedź
1 1P: (0, 1), P: (0, 2), D: (1, 2), L: (1, 1).
Czy kratka nad (0, 2) leży na planszy 3 × 3?
int n = 3;
pair<int, int> p = {0, 2};
int nw = p.first - 1;
cout << (nw >= 0 && nw < n);
Pokaż odpowiedź
0Nad wierszem 0 jest wiersz −1 — poza planszą.
Ile pól ma do wyboru skoczek z pola (0, 1)?
pair<int, int> skok[8] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
                          {1, -2}, {1, 2}, {2, -1}, {2, 1}};
int ile = 0;
for (auto [dw, dk] : skok) {
    int nw = 0 + dw, nk = 1 + dk;
    if (nw >= 0 && nw < 8 && nk >= 0 && nk < 8) ile++;
}
cout << ile;
Pokaż odpowiedź
3Skoki w górę wychodzą poza planszę. Zostają (1, 3), (2, 0) i (2, 2) — skok (1, −1) też wypada poza nią.
Ć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 Robotłatwe✓ zaliczone Polecenia G, P, D, L i tablica kroków. Gdzie skończy robot i jak daleko od startu? pair<int, int> ruch[4]find w "GPDL"abs Rozwiąż 6.2 Robot w pokojuśrednie✓ zaliczone Robot omija ściany i nie wychodzi poza pokój. Gdzie skończy i ile poleceń się nie udało? brzegi planszyściany #nowa pozycja Rozwiąż 6.3 Ile różnych kratek?średnie✓ zaliczone Robot chodzi po planszy i wraca w te same miejsca. Ile różnych kratek odwiedził? tablica odwiedzonych parczy już byłopozycja jako para Rozwiąż 6.4 Ruchy skoczkałatwe✓ zaliczone Pole w zapisie szachowym (e4). Na ile pól może skoczyć skoczek? Osiem skoków jako pary. pair<int, int> skok[8]c - 'a'brzegi szachownicy Rozwiąż 6.5 Spacer z obrotamiśrednie✓ zaliczone Polecenia „F k”, R i L: idź k kroków przed siebie albo obróć się. Kierunek to numer od 0 do 3. kierunek jako numer(d + 1) % 4(d + 3) % 4 Rozwiąż 6.6 Najbardziej otoczona kratkaśrednie✓ zaliczone Która wolna kratka ma najwięcej ścian wśród ośmiu sąsiadów? Remis rozstrzyga para (wiersz, kolumna). osiem kierunkówpary krokównajmniejsza (w, k) Rozwiąż 6.7 Ile ruchów króla?łatwe✓ zaliczone Król idzie o jedno pole, także po skosie. Ile ruchów potrzebuje z (w₁, k₁) do (w₂, k₂)? max i absruch po skosiepozycje jako pary Rozwiąż 6.8 Powrót do domuśrednie✓ zaliczone Po którym poleceniu robot pierwszy raz wróci do kratki startowej? pozycja jako parap == startbreak Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Sortowanie par: sort i klucz na pierwszym miejscu

W części 3 porządkowałeś trzy pary ręcznie, trzema zamianami. Dla stu albo stu tysięcy par tak się nie da. C++ ma gotowe polecenie sort, które układa całą tablicę w kolejności rosnącej — jedną linijką. Jak sort działa w środku i jakie są różne sposoby sortowania, poznasz dokładnie w lekcji o sortowaniu. Tutaj wystarczy Ci jedno: sort porównuje elementy tak samo jak operator <. A skoro pary umieją się porównywać — pary układają się same, najpierw po first, a przy remisie po second.

sort — cała tablica w porządku jedną linijką

Zapis sort(a, a + n); układa rosnąco pierwsze n pudełek tablicy a, od a[0] do a[n - 1]. Drugi argument, a + n, czytaj jako „aż do pudełka n — ale bez niego”. To ta sama zasada co w pętli i < n. Polecenie działa na liczbach, napisach (alfabetycznie, jak w lekcji o napisach) i na parach.

sort_liczby.cpp
int a[6] = {5, 2, 9, 1, 5, 3};
sort(a, a + 6);                    // całe 6 pudełek
for (int i = 0; i < 6; i++) {
    cout << a[i] << " ";
}
cout << "\n";
string s[4] = {"ola", "ala", "ewa", "ela"};
sort(s, s + 4);                    // napisy — alfabetycznie
for (int i = 0; i < 4; i++) {
    cout << s[i] << " ";
}
cout << "\n";
▶ Wyjście
1 2 3 5 5 9 ala ela ewa ola

sort jest w bibliotece <algorithm> (jest też w <bits/stdc++.h>). Zmienia tablicę w miejscu — po sortowaniu stara kolejność przepada.

Gdy tablica ma zapas, na przykład int a[1005], a liczb jest n, sortujesz tylko zajęte pudełka: sort(a, a + n). Gdybyś napisał sort(a, a + 1005), do sortowania trafiłyby też puste pudełka.

Sortowanie jest szybkie: sto tysięcy liczb układa w ułamku sekundy.

Pary układają się same

Posortujmy tablicę par. sort używa porównania par z części 3, więc pary ustawiają się według first, a pary z takim samym first — według second. Nie piszesz ani jednej linijki porównania.

Po sort(t, t + 5): pary z first = 1 stoją obok siebie (niebieskie) i między sobą są ułożone po second: 50, potem 60. Tak samo pary z first = 3 (zielone): 20, potem 100.
sort_pary.cpp
pair<int, int> t[5] = {{3, 100}, {1, 50}, {3, 20}, {2, 70}, {1, 60}};
sort(t, t + 5);
for (int i = 0; i < 5; i++) {
    cout << t[i].first << "-" << t[i].second << " ";
}
cout << "\n";
▶ Wyjście
1-50 1-60 2-70 3-20 3-100

Najważniejsze zdanie tej części: kolejność przegródek w parze decyduje o kolejności sortowania. To, co ma decydować najbardziej, wkładasz do first. To, co ma rozstrzygać remisy — do second.

Klucz na pierwsze miejsce: ranking

Chcemy wypisać uczniów od najlepszego. Dane przychodzą jako „imię punkty”, ale sortować chcemy po punktach — więc punkty idą do first, a imię do second. Wczytujemy od razu we właściwe przegródki. sort ułoży rosnąco, czyli od najsłabszego; wystarczy wypisać tablicę od końca.

ranking_od_konca.cpp
int n;
cin >> n;
pair<int, string> t[1005];                 // (punkty, imię)
for (int i = 0; i < n; i++) {
    cin >> t[i].second >> t[i].first;      // najpierw imię, potem punkty
}
sort(t, t + n);
for (int i = n - 1; i >= 0; i--) {         // od końca = malejąco
    cout << t[i].second << " " << t[i].first << "\n";
}
▶ Wejście
4 Ola 90 Jan 75 Ewa 90 Igor 60
▶ Wyjście
Ola 90 Ewa 90 Jan 75 Igor 60
ranking_minus.cpp
int n;
cin >> n;
pair<int, string> t[1005];                 // (-punkty, imię)
for (int i = 0; i < n; i++) {
    int p;
    cin >> t[i].second >> p;
    t[i].first = -p;                       // minus: więcej punktów = mniejsza para
}
sort(t, t + n);
for (int i = 0; i < n; i++) {
    cout << t[i].second << " " << -t[i].first << "\n";
}
▶ Wejście
4 Ola 90 Jan 75 Ewa 90 Igor 60
▶ Wyjście
Ewa 90 Ola 90 Jan 75 Igor 60

Spójrz na remis Oli i Ewy. Lewy program wypisuje tablicę od końca, więc przy remisie odwraca także kolejność imion: Ola przed Ewą. Zwykle w rankingu przy remisie chcemy kolejności alfabetycznej — i to daje prawy program ze sztuczką z minusem z części 3. Para (−90, „Ewa”) jest mniejsza od (−90, „Ola”), a obie są mniejsze od (−75, „Jan”). Sortujemy normalnie, wypisujemy od początku, a przy wypisywaniu cofamy minus.

Przepis na sortowanie według kilku kryteriów 1) Wypisz kryteria od najważniejszego. 2) Ułóż z nich parę (albo parę w parze) w tej samej kolejności. 3) Kryterium, w którym lepiej jest „więcej”, zapisz z minusem. 4) Posortuj i wypisz od początku, cofając minusy. Gdy na końcu potrzebujesz jeszcze numeru zawodnika, dopisz go jako ostatnie kryterium — remisy rozstrzygnie wtedy numer.

Para (wartość, numer): gdzie stały przed sortowaniem

Sortowanie gubi starą kolejność. A często trzeba wiedzieć, skąd przyszła każda liczba — który zawodnik, który dzień, które pudełko. Rozwiązanie znasz z części 4: zanim posortujesz, zamień każdą wartość w parę (wartość, numer). Numer pojedzie razem z wartością, a przy równych wartościach o kolejności zdecyduje właśnie on.

gdzie_staly.cpp
int n;
cin >> n;
pair<int, int> t[1005];          // (wartość, numer na wejściu)
for (int i = 0; i < n; i++) {
    cin >> t[i].first;
    t[i].second = i + 1;
}
sort(t, t + n);
for (int i = 0; i < n; i++) {
    cout << t[i].second << " ";   // numery od najmniejszej wartości
}
cout << "\n";
▶ Wejście
5 40 10 30 10 20
▶ Wyjście
2 4 5 3 1
Po sortowaniu pary (wartość, numer). Dwie dziesiątki stoją obok siebie, a między sobą — według numerów: najpierw liczba numer 2, potem numer 4.

Najmniejsza wartość, 10, stała na wejściu jako druga i czwarta. Dlatego wynik zaczyna się od numerów 2 i 4.

Po sortowaniu: miejsca w rankingu

Posortowana tablica to dopiero początek. Prawie zawsze trzeba jeszcze przejść po niej pętlą i coś policzyć. Klasyczne zadanie: miejsca w rankingu, gdy zawodnicy z taką samą liczbą punktów dzielą miejsce (ex aequo), a następne miejsce jest odpowiednio dalej: 1, 1, 3, 4.

ex_aequo.cpp
int n;
cin >> n;
pair<int, string> t[1005];                // (-punkty, imię)
for (int i = 0; i < n; i++) {
    int p;
    cin >> t[i].second >> p;
    t[i].first = -p;
}
sort(t, t + n);
int miejsce = 1;
for (int i = 0; i < n; i++) {
    if (i > 0 && t[i].first != t[i - 1].first) {
        miejsce = i + 1;                  // nowy wynik — nowe miejsce
    }
    cout << miejsce << ". " << t[i].second << " " << -t[i].first << "\n";
}
▶ Wejście
4 Ola 90 Jan 75 Ewa 90 Igor 60
▶ Wyjście
1. Ewa 90 1. Ola 90 3. Jan 75 4. Igor 60

Miejsce zmienia się tylko wtedy, gdy punkty różnią się od poprzedniego zawodnika — i wtedy jest równe numerowi pozycji w posortowanej tablicy (licząc od 1). Ewa i Ola mają po 90 punktów, więc obie są pierwsze. Jan jest trzeci, bo przed nim stoją dwie osoby.

Warunek i > 0 stoi na początku z tego samego powodu co zawsze: dla i = 0 nie ma t[i - 1].

Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int a[5] = {4, 1, 3, 1, 2};
sort(a, a + 5);
cout << a[0] << a[4];
Pokaż odpowiedź
14Po sortowaniu: 1 1 2 3 4. Pierwszy element to 1, ostatni — 4.
Co wypisze ten fragment?
pair<int, int> t[3] = {{2, 1}, {1, 9}, {2, 0}};
sort(t, t + 3);
cout << t[1].first << t[1].second;
Pokaż odpowiedź
20Po sortowaniu: (1, 9), (2, 0), (2, 1). Środkowa para to (2, 0).
Wielkie litery. Co wypisze ten fragment?
string s[3] = {"kot", "Kot", "ala"};
sort(s, s + 3);
cout << s[0];
Pokaż odpowiedź
KotNapisy sortują się jak w lekcji o napisach: wielkie litery są przed małymi, więc „Kot” wyprzedza nawet „ala”.
Sortujemy tylko część. Co wypisze ten fragment?
int a[5] = {5, 4, 3, 2, 1};
sort(a, a + 3);
cout << a[0] << a[3];
Pokaż odpowiedź
32Sortujemy tylko pudełka 0–2: 5 4 3 zmienia się w 3 4 5. Pudełka 3 i 4 zostają: 2 i 1.
Sztuczka z minusem. Co wypisze ten fragment?
pair<int, string> t[2] = {{-5, "Ola"}, {-7, "Jan"}};
sort(t, t + 2);
cout << t[0].second;
Pokaż odpowiedź
Jan−7 < −5, więc para Jana stoi pierwsza — Jan ma więcej punktów (7).
Co wypisze ten fragment?
pair<int, int> t[3] = {{7, 1}, {5, 2}, {7, 3}};
sort(t, t + 3);
cout << t[2].second;
Pokaż odpowiedź
3Po sortowaniu: (5, 2), (7, 1), (7, 3). Przy remisie siódemek decyduje second.
Ć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 →

Pary na olimpiadzie: przedziały i zdarzenia

Połączenie par z sortowaniem to jeden z najczęstszych schematów w zadaniach olimpijskich. Typowa historia: na wejściu jest mnóstwo przedziałów — wizyt w sklepie, wykładów, pomalowanych kawałków płotu — i trzeba odpowiedzieć na pytanie, które dla nieposortowanych danych wymagałoby porównywania każdego z każdym. Po posortowaniu par wystarcza jedno przejście pętlą. W tej części poznasz cztery takie schematy: scalanie przedziałów, zdarzenia, najbliższą parę i zachłanny wybór. Na koniec zobaczysz, dlaczego to wszystko jest tak szybkie.

Scalanie przedziałów

Mamy kilka przedziałów, które mogą na siebie nachodzić — na przykład godziny, w których działała lampa. Chcemy je połączyć w rozłączne kawałki. Pomysł: posortuj przedziały po początku. Wtedy idziesz od lewej i trzymasz bieżący kawałek. Kolejny przedział albo zaczyna się przed końcem bieżącego (nachodzi na niego — rozszerzasz bieżący), albo za nim (bieżący jest gotowy — wypisujesz go i zaczynasz nowy).

Po sortowaniu: (1, 3) i (2, 4) nachodzą na siebie — razem dają [1, 4] (niebieskie). (5, 8) zaczyna się za czwórką, więc to nowy kawałek (zielony). (10, 12) — kolejny (pomarańczowy).
scalanie.cpp
int n;
cin >> n;
pair<int, int> t[1005];                 // (początek, koniec)
for (int i = 0; i < n; i++) {
    cin >> t[i].first >> t[i].second;
}
sort(t, t + n);                         // po początkach
pair<int, int> akt = t[0];              // bieżący kawałek
for (int i = 1; i < n; i++) {
    if (t[i].first <= akt.second) {     // nachodzi — rozszerzamy
        akt.second = max(akt.second, t[i].second);
    } else {                            // przerwa — bieżący gotowy
        cout << akt.first << " " << akt.second << "\n";
        akt = t[i];
    }
}
cout << akt.first << " " << akt.second << "\n";   // ostatni kawałek
▶ Wejście
4 5 8 1 3 2 4 10 12
▶ Wyjście
1 4 5 8 10 12

Dlaczego max(akt.second, t[i].second), a nie po prostu t[i].second? Bo nowy przedział może leżeć w środku bieżącego: [1, 10] i [2, 3] dają razem [1, 10], a nie [1, 3].

Ostatni kawałek wypisujemy po pętli — za nim nie przyszedł już żaden przedział, który by go „zamknął”. To ten sam problem co ostatni kawałek przy cięciu napisu po przecinkach w lekcji o napisach.

Zdarzenia: (czas, +1) i (czas, −1)

Ile osób było w sklepie naraz w najbardziej tłocznej chwili? Każda wizyta to przedział (wejście, wyjście). Sztuczka: rozbij każdą wizytę na dwa zdarzenia — parę (czas wejścia, +1) i parę (czas wyjścia, −1). Posortuj wszystkie zdarzenia i przejdź po nich, dodając drugie przegródki: licznik pokazuje, ile osób jest w sklepie w danej chwili.

zdarzenia.cpp
int n;
cin >> n;
pair<int, int> z[2005];               // (czas, +1 wejście / -1 wyjście)
for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    z[2 * i] = {a, 1};
    z[2 * i + 1] = {b, -1};
}
sort(z, z + 2 * n);
int teraz = 0, najwiecej = 0;
for (int i = 0; i < 2 * n; i++) {
    teraz += z[i].second;
    najwiecej = max(najwiecej, teraz);
}
cout << najwiecej << "\n";
▶ Wejście
3 1 5 2 6 5 8
▶ Wyjście
2
zdarzenieteraznajwięcej
(1, +1)11
(2, +1)22
(5, −1)12
(5, +1)22
(6, −1)12
(8, −1)02

Zwróć uwagę na chwilę 5: jedna osoba wychodzi, druga wchodzi. Para (5, −1) jest mniejsza od (5, +1), więc wyjście liczy się przed wejściem — i w sklepie nie robi się na moment troje ludzi. Porządek par sam rozstrzygnął ten remis. Gdyby treść mówiła, że osoby wychodząca i wchodząca o 5 jeszcze się spotykają, wejście musiałoby stać przed wyjściem — wtedy zapisz wejście jako (czas, 0), wyjście jako (czas, 1) i przy liczeniu dla 0 dodawaj, a dla 1 odejmuj.

Najbliższa para po sortowaniu

Na prostej drodze stoi n domów. Jaka jest najmniejsza odległość między dwoma domami? Porównywanie każdego z każdym to n² / 2 par — dla stu tysięcy domów za dużo. Po posortowaniu pozycji odpowiedź jest dużo prostsza: dwa najbliższe domy muszą stać obok siebie w posortowanej kolejności. Wystarczy sprawdzić n − 1 par sąsiadów.

najblizsze.cpp
int n;
cin >> n;
int d[1005];
for (int i = 0; i < n; i++) {
    cin >> d[i];
}
sort(d, d + n);
int najmniej = 2000000000;
for (int i = 0; i + 1 < n; i++) {
    najmniej = min(najmniej, d[i + 1] - d[i]);   // tylko sąsiedzi
}
cout << najmniej << "\n";
▶ Wejście
5 30 4 17 21 9
▶ Wyjście
4

Po sortowaniu: 4, 9, 17, 21, 30. Różnice sąsiadów to 5, 8, 4, 9 — najmniejsza to 4 (domy w 17 i 21). Dom w 4 i dom w 21 nie mogą być bliżej siebie niż 17 i 21, bo między nimi stoi właśnie 17.

A gdyby trzeba było podać numery tych domów? Wtedy sortujesz pary (pozycja, numer) — dokładnie jak w części 7. To jedno z ćwiczeń.

Zachłanny wybór: najwięcej wykładów

W auli odbywają się wykłady, każdy od pewnej godziny do pewnej godziny. Chcesz pójść na jak najwięcej z nich, ale nie możesz być na dwóch naraz. Który wykład wybrać najpierw? Okazuje się, że zawsze najlepiej wybrać ten, który najwcześniej się kończy — zostawia najwięcej czasu na resztę. Potem z pozostałych, które zaczynają się nie wcześniej niż koniec wybranego, znowu ten kończący się najwcześniej. Taki sposób — „bierz to, co teraz wygląda najlepiej” — nazywa się algorytmem zachłannym.

Żeby sortować po końcu, koniec musi stać w first. Dlatego wczytujemy wykład do pary (koniec, początek).

wyklady.cpp
int n;
cin >> n;
pair<int, int> w[1005];               // (koniec, początek)
for (int i = 0; i < n; i++) {
    cin >> w[i].second >> w[i].first;  // wejście: początek koniec
}
sort(w, w + n);                       // od najwcześniej kończącego się
int ile = 0, wolneOd = -1;            // od kiedy jesteśmy wolni
for (int i = 0; i < n; i++) {
    if (w[i].second >= wolneOd) {     // zaczyna się, gdy jesteśmy wolni
        ile++;
        wolneOd = w[i].first;
    }
}
cout << ile << "\n";
▶ Wejście
4 1 4 3 5 0 6 5 7
▶ Wyjście
2

Po sortowaniu po końcach: [1, 4], [3, 5], [0, 6], [5, 7]. Bierzemy [1, 4] — jesteśmy wolni od 4. [3, 5] zaczyna się o 3 — za wcześnie. [0, 6] też. [5, 7] zaczyna się o 5, czyli gdy jesteśmy wolni — bierzemy. Razem 2 wykłady.

Intuicja, dlaczego to działa: wykład, który kończy się najwcześniej, „zabiera” najmniej czasu z przyszłości. Każdy inny pierwszy wybór kończyłby się później i mógłby tylko przeszkodzić kolejnym. Dowód takiego algorytmu to temat na dalsze lekcje — tu ważne, żeby zapamiętać schemat.

Ile to wszystko kosztuje?

Dlaczego sortowanie tak bardzo przyspiesza? Porównanie każdego z każdym to około n² / 2 operacji. sort potrzebuje około n · log₂n porównań — log₂n to „ile razy trzeba podzielić n przez 2, żeby dojść do 1”, dla miliona to tylko około 20. Po sortowaniu wystarcza jedno przejście pętlą, czyli n kroków.

nkażdy z każdym (n² / 2)sort (n · log₂n)
1 000500 000 — błyskawicznieokoło 10 000
100 0005 000 000 000 — kilkanaście sekundokoło 1 700 000 — ułamek sekundy
1 000 000500 000 000 000 — godzinyokoło 20 000 000 — ułamek sekundy
Duże tablice par — poza main Para dwóch liczb int zajmuje 8 bajtów, więc tablica stu tysięcy par to 800 KB. Tak duże tablice, tak jak w lekcji o tablicach, deklaruj przed main — globalnie. W środku main potrafią wysypać program przy starcie, szczególnie na Windowsie.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pary na kartce — osobno first i second — i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Czy te przedziały się połączą?
pair<int, int> a = {1, 5}, b = {4, 9};
cout << (b.first <= a.second);
Pokaż odpowiedź
1b zaczyna się w 4, a a kończy w 5 — nachodzą na siebie. Razem dają [1, 9].
Zdarzenia w tej samej chwili. Co wypisze ten fragment?
pair<int, int> wyjscie = {5, -1}, wejscie = {5, 1};
cout << (wyjscie < wejscie);
Pokaż odpowiedź
1Czas równy, więc decyduje second: −1 < 1. Po sortowaniu wyjście będzie przed wejściem.
Co wypisze ten fragment?
pair<int, int> w[3] = {{4, 1}, {6, 0}, {5, 3}};
sort(w, w + 3);
cout << w[1].second;
Pokaż odpowiedź
3Po sortowaniu po końcach: (4, 1), (5, 3), (6, 0). Środkowa para ma second = 3.
Scalanie: przedział w środku. Co wypisze ten fragment?
pair<int, int> akt = {1, 10}, t = {2, 3};
if (t.first <= akt.second) akt.second = max(akt.second, t.second);
cout << akt.first << " " << akt.second;
Pokaż odpowiedź
1 10[2, 3] leży w środku [1, 10], więc koniec się nie zmienia — dzięki max.
Serie jako pary. Który znak stoi na pozycji 4?
pair<char, int> s[3] = {{'a', 3}, {'b', 1}, {'c', 2}};
int p = 4, i = 0;
while (p > s[i].second) {
    p -= s[i].second;
    i++;
}
cout << s[i].first;
Pokaż odpowiedź
bNapis to aaabcc. Pozycja 4 (licząc od 1): trzy litery a zajmują pozycje 1–3, więc czwarta to b.
Najbliższe po sortowaniu. Co wypisze ten fragment?
int d[4] = {10, 1, 7, 15};
sort(d, d + 4);
int m = 100;
for (int i = 0; i + 1 < 4; i++) m = min(m, d[i + 1] - d[i]);
cout << m;
Pokaż odpowiedź
3Po sortowaniu: 1, 7, 10, 15. Różnice sąsiadów: 6, 3, 5. Najmniejsza to 3.
Ć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 Pomalowany płotśrednie✓ zaliczone Malarze malowali kawałki płotu, czasem po sobie. Ile jest pomalowanych części i jaka ich łączna długość? scalanie przedziałówsort po początkachostatni kawałek Rozwiąż 8.2 Najtłoczniejsza chwilaśrednie✓ zaliczone Ile osób było naraz w muzeum w najtłoczniejszej chwili — i kiedy pierwszy raz tyle się zebrało? zdarzenia (czas, ±1)sortpierwsza chwila rekordu Rozwiąż 8.3 Najbliższe domyśrednie✓ zaliczone Które dwa domy przy drodze stoją najbliżej siebie? Sortuj pary (pozycja, numer) i patrz na sąsiadów. para (pozycja, numer)sortsąsiedzi po sortowaniu Rozwiąż 8.4 Najwięcej wykładówśrednie✓ zaliczone Zachłannie: zawsze wybieraj wykład, który najwcześniej się kończy. Ile ich wybierzesz i które? sort po końcachzachłanny wybór{{koniec, początek}, numer} Rozwiąż 8.5 Litera na pozycjiśrednie✓ zaliczone Napis zapisany jako pary (litera, ile razy) jest gigantyczny. Która litera stoi na pozycji p? pair<char, long long>serieodejmowanie długości Rozwiąż 8.6 Kolejka do lekarzaśrednie✓ zaliczone Pacjenci przychodzą o różnych porach. Kiedy każdy z nich wyjdzie z gabinetu? sort po przyjściu{przyjście, numer}symulacja Rozwiąż 8.7 Najdłuższa ciszałatwe✓ zaliczone Godziny dzwonków jako pary (h, m) — posortuj je i znajdź najdłuższą przerwę między kolejnymi. sort par (h, m)różnica minutHH:MM Rozwiąż 8.8 Awans do finałuśrednie✓ zaliczone Do finału awansuje k najlepszych. Wypisz ich numery rosnąco — sortując dwa razy. {{-punkty, czas}, numer}sortdrugie sortowanie Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Baza zadań: pary w praktyce

Znasz już wszystko, co potrzebne: first i second, klamry i make_pair, punkty, godziny, ułamki i przedziały zapisane jako pary, kolejność par i sztuczkę z minusem, tablice par i parę (wartość, numer), rozpakowywanie i pary w parach, kierunki na planszy, sortowanie par oraz scalanie przedziałów, zdarzenia i zachłanny wybór. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie — prostokąty, punkty niezdominowane, balony, pole działki — a na końcu trudne, z mrówką Langtona, największym trójkątem, pokryciem odcinka i wielkim finałem.

Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak modulo, tablice czy napisy. 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 z parami

Tworzenie i dostęp

pair<string, int> u = {"Ola", 95};
u.first   u.second    // bez nawiasów!
u = {"Jan", 87};
pair<int, int> p;    // (0, 0)

Wczytujesz i wypisujesz przegródki osobno — cout << p się nie skompiluje.

Pary z życia

abs(a.first - b.first)
  + abs(a.second - b.second)
m = (h * 60 + min + k) % 1440;
{max(a1, b1), min(a2, b2)}

Punkt, godzina, ułamek, przedział. Część wspólna jest pusta, gdy początek > koniec.

Porównywanie

(a, b) < (c, d):  a < c,
  albo a == c i b < d
{punkty, -czas}   // więcej, mniej
max(p, q)   min(p, q)

Najważniejsze kryterium do first. „Mniej znaczy lepiej” — minus.

Tablica par

pair<int, int> t[1005];
cin >> t[i].first >> t[i].second;
best = min(best, make_pair(x, i));

Para (wartość, numer) — przy remisie wygrywa pierwsze wystąpienie.

Rozpakowywanie i trójki

auto [a, b] = p;      // kopie
auto &[a, b] = p;     // oryginał
pair<int, pair<int, int>> d =
    {rok, {mies, dzien}};

Daty jako (rok, (miesiąc, dzień)) porównują się chronologicznie.

Plansza

pair<int, int> ruch[4] =
  {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
nw = w + dw;  nk = k + dk;
d = (d + 1) % 4;   // w prawo

Najpierw sprawdź brzegi, potem zajrzyj do kratki.

Sortowanie

sort(t, t + n);
// ranking: {-punkty, imie}
// stara pozycja: {wartosc, i}
if (i > 0 && t[i] != t[i - 1]) ...

Kolejność przegródek = kolejność sortowania.

Przedziały i zdarzenia

sort po początkach → scalanie
{czas, +1}, {czas, -1} → licznik
sort po końcach → zachłanny wybór

Duże tablice par deklaruj przed main.

Jak rozwiązywać zadania z parami 1) Zapytaj: które wartości należą do siebie? Imię i punkty, x i y, początek i koniec — to pary. 2) Zdecyduj, co jest w first, a co w second — i zapisz to w komentarzu. 3) Jeśli trzeba porównywać albo sortować, ułóż przegródki od najważniejszego kryterium; „mniej znaczy lepiej” zapisz z minusem. 4) Gdy po sortowaniu potrzebujesz starej pozycji, dołóż numer do pary. 5) Przy przedziałach zastanów się, czy końce się liczą (czy [1, 5] i [5, 8] nachodzą na siebie) — to zawsze jest w treści. 6) Przetestuj skrajności: jedna para, wszystkie pary równe, remisy na first, liczby ujemne.
łatwe

Rozgrzewka · zadania 1–10

Jeden pomysł naraz: czwarty wierzchołek, aukcja, trasa kuriera, wspólna część przedziałów, dzwonki, pociągi, wieże, kino, szachownica Polibiusza i skok w dal.

1 Czwarty wierzchołekłatwe✓ zaliczone Znasz trzy wierzchołki prostokąta o bokach równoległych do osi. Gdzie jest czwarty? punkty jako parywartość, która występuje razif / else Rozwiąż 2 Aukcjałatwe✓ zaliczone Oferta liczy się tylko wtedy, gdy przebija najlepszą o co najmniej k zł. Kto wygra i za ile? {kwota, imie}warunek przebiciaBRAK Rozwiąż 3 Trasa kurierałatwe✓ zaliczone Kurier wyjeżdża z bazy, odwiedza punkty po kolei i wraca. Ile przejedzie ulicami miasta? punkt poprzedni i obecnyabslong long Rozwiąż 4 Wspólny wolny czasłatwe✓ zaliczone Każdy z przyjaciół jest wolny w pewnym przedziale. Kiedy wszyscy naraz? Późniejszy początek, wcześniejszy koniec. przedziałymax początków, min końcówBRAK Rozwiąż 5 Dzwonkiłatwe✓ zaliczone Lekcje trwają po 45 minut. Czy o podanej godzinie trwa lekcja, przerwa, czy jest przed albo po lekcjach? godziny jako paryminuty od północyprzedziały [od, do) Rozwiąż 6 Najbliższy pociągłatwe✓ zaliczone Rozkład jazdy to godziny odjazdów. O której odjedzie najbliższy pociąg? Może dopiero jutro. godziny jako parynajmniejsza ≥ tjutro rano Rozwiąż 7 Wieże na szachownicyłatwe✓ zaliczone Ile par wież widzi się nawzajem w tym samym wierszu albo kolumnie? Policz wieże w każdym wierszu i kolumnie. pozycje jako paryliczniki wierszy i kolumnk · (k − 1) / 2 Rozwiąż 8 Rezerwacje w kiniełatwe✓ zaliczone Rezerwacje przychodzą jedna po drugiej. Miejsce wolne — OK, zajęte — ZAJETE. Ile zostało wolnych? miejsce jako paratablica boollicznik wolnych Rozwiąż 9 Szachownica Polibiuszałatwe✓ zaliczone Starożytny szyfr: każda litera to para (wiersz, kolumna) w kwadracie 5 × 5. pozycja litery jako parafindp / 5 i p % 5 Rozwiąż 10 Skok w dalłatwe✓ zaliczone Każdy ma trzy próby. Wygrywa najlepszy skok, a przy remisie — drugi najlepszy. Para {najlepszy, drugi}. {najlepszy, drugi}ostro większaspalone próby Rozwiąż
średnie

Średnie · zadania 11–20

Kilka sztuczek naraz: przecięcie prostokątów, punkty od najbliższego, punkty niezdominowane, symetria, najbliższe miasto, pole figury, balony, kolizje w planie i pole działki.

11 Przecięcie prostokątówśrednie✓ zaliczone Dwa prostokąty o bokach wzdłuż osi. Jakie pole ma ich część wspólna? rogi jako parymax i minlong long Rozwiąż 12 Od najbliższegośrednie✓ zaliczone Posortuj punkty według odległości od (0, 0), a przy remisie według (x, y). Klucz {x² + y², {x, y}}. para w parzesortodległość bez pierwiastka Rozwiąż 13 Punkty niezdominowaneśrednie✓ zaliczone Punkt jest zdominowany, gdy inny ma i x, i y nie mniejsze. Które punkty nikt nie dominuje? każdy z każdym albo sortparyfront Pareto Rozwiąż 14 Symetria względem środkaśrednie✓ zaliczone Czy zbiór punktów wygląda tak samo po obrocie o pół obrotu wokół (0, 0)? Dla (x, y) musi być (−x, −y). szukanie parypara == parasort + porównanie Rozwiąż 15 Najbliższe miastośrednie✓ zaliczone Dla każdego punktu na mapie wskaż najbliższe miasto. Remis? Wygrywa nazwa wcześniejsza alfabetycznie. {odległość, nazwa}mintablica miast Rozwiąż 16 Pole figury z prostokątówśrednie✓ zaliczone Prostokąty nakładają się na siebie. Ile wynosi pole całej figury? Zamaluj kratki na planszy. rogi jako parytablica bool 2Dkratki jednostkowe Rozwiąż 17 Balony i strzałyśrednie✓ zaliczone Pionowa strzała przebija każdy balon, nad którym przeleci. Ile strzał wystarczy? Zachłannie, po końcach. sort po końcachzachłanny wybórprzedziały Rozwiąż 18 Kolizje w planieśrednie✓ zaliczone Ile par wydarzeń w kalendarzu nachodzi na siebie? Dwa przedziały kolidują, gdy max(początków) < min(końców). przedziały [od, do)każdy z każdymmax i min Rozwiąż 19 Pole działkiśrednie✓ zaliczone Geodeta podał kolejne narożniki działki. Policz jej pole wzorem „sznurowadłowym”. wierzchołki jako parywzór Gaussalong long i połówka Rozwiąż 20 Najczęściej odwiedzane miejsceśrednie✓ zaliczone Robot krąży po planszy. W której kratce bywał najczęściej? Remis rozstrzyga para (wiersz, kolumna). tablica par (pozycja, licznik)szukaj albo dopisznajmniejsza para Rozwiąż
trudne

Trudne · zadania 21–28

Mrówka Langtona, największy trójkąt, pokrycie odcinka, gdzie zbudować sklep, prostokąty z punktów, robot z przeszkodami — a na koniec wielki finał: klasyfikacja olimpiady.

21 Mrówka Langtonatrudne✓ zaliczone Na białym polu w prawo, na czarnym w lewo, przemaluj i krok. Symulacja z kierunkami jako parami. kierunki i obrotyplansza z przesunięciemsymulacja Rozwiąż 22 Największy trójkąttrudne✓ zaliczone Spośród stu punktów wybierz trzy tworzące trójkąt o największym polu. Iloczyn wektorowy na parach. trzy pętleiloczyn wektorowypołówka pola Rozwiąż 23 Pokrycie odcinkatrudne✓ zaliczone Najmniej odcinków, które razem zakryją cały odcinek [0, L]. Zachłannie: zawsze sięgaj najdalej. sort po początkachzachłanny wybórNIE Rozwiąż 24 Gdzie zbudować sklep?trudne✓ zaliczone Sklep ma być jak najbliżej wszystkich domów (ulicami w kratkę). Mediana x-ów i mediana y-ów! sortmedianaodległość taksówkarza Rozwiąż 25 Prostokąty z punktówtrudne✓ zaliczone Ile prostokątów o bokach wzdłuż osi ma wszystkie cztery wierzchołki wśród danych punktów? pary jako przekątnetablica bool 2Dkażdy z każdym Rozwiąż 26 Robot z przeszkodamitrudne✓ zaliczone Robot chodzi po planszy z obrotami i staje przed ścianą. Gdzie skończy i ile różnych pól odwiedził? kierunki i obrotybrzegi i ścianyodwiedzone pola Rozwiąż 27 Wspólny termin spotkaniatrudne✓ zaliczone Dwie osoby, dwa kalendarze zajęć. Kiedy najwcześniej obie mają wolne L minut naraz? scalanie przedziałówluki między przedziałamiHH:MM Rozwiąż 28 Wielki finał: klasyfikacja olimpiadytrudne✓ zaliczone Pełna klasyfikacja: suma punktów, potem liczba zadań za 100, potem imię — z miejscami ex aequo. para w parzesortex aequo Rozwiąż

Częste błędy i dobre praktyki

🧩
p.first, nie p.first()
first i second to nazwy przegródek, a nie polecenia — piszesz je bez nawiasów. Z nawiasami program się nie skompiluje.
🖨️
cout << p nie działa
Para nie umie się wypisać ani wczytać sama. Pracuj na przegródkach: cin >> p.first >> p.second; i wypisuj je w formacie, którego chce zadanie.
🔀
Kolejność typów i wartości
pair<int, string> ma liczbę w first. Klamry {"Ola", 95} do niej nie pasują. Typy w nawiasach ostrych i wartości w klamrach muszą iść w tej samej kolejności.
⚖️
second tylko przy remisie
(1, 1000) < (2, 0), bo o wyniku decyduje first. second liczy się dopiero wtedy, gdy first są równe — jak druga litera w słowniku.
🥇
Najważniejsze do first
Sortujesz po punktach? Punkty idą do first. Godziny porównujesz? (godzina, minuta), nie odwrotnie. Kolejność przegródek to kolejność kryteriów.
➖
„Mniej znaczy lepiej” — minus
Więcej punktów, ale mniej czasu? Para {punkty, -czas} i szukasz największej. Nie zapomnij cofnąć minusa przy wypisywaniu.
🏷️
Numer w parze
Po sortowaniu stara kolejność przepada. Jeśli będzie Ci potrzebna, zrób parę (wartość, numer) jeszcze przed sortowaniem.
📏
sort(t, t + n)
Sortuj tylko zajęte pudełka. sort(t, t + 1005) wciągnie do sortowania puste pary (0, 0) i rozjedzie wynik.
🔁
auto [a, b] to kopie
Zmiany w rozpakowanych zmiennych nie wracają do pary. Chcesz zmieniać parę — pisz auto &[a, b]. Pętla for (auto [a, b] : t) idzie po całej tablicy, także po zapasie.
🧭
Brzegi przed kratką
Na planszy najpierw sprawdź, czy nowa pozycja leży na planszy, a dopiero potem zaglądaj do p[nw][nk]. Obrót w lewo to (d + 3) % 4, nie (d - 1) % 4.
📐
Czy końce się liczą?
Przedziały [1, 5] i [5, 8] — nachodzą na siebie czy nie? To zależy od treści. Zdecyduj raz i sprawdź warunek (<= czy <) oraz kolejność zdarzeń w tej samej chwili.
🌍
Duże tablice par globalnie
Sto tysięcy par to 800 KB. Takie tablice deklaruj przed main, a wyniki mnożenia współrzędnych trzymaj w long long.

Co dalej?

Pary będą Ci towarzyszyć w każdym kolejnym temacie: punkty na planszy, krawędzie grafów, wyniki zawodników. Następna lekcja to vector — tablica, która sama rośnie, tak jak napis. Bardzo często będziesz w nim trzymać właśnie pary. Potem przyjdzie sortowanie, w którym zobaczysz, jak sort działa w środku i jak sortować według własnych zasad. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.