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ć.
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.
Pierwsza para i pary z życia
first i second, a potem punkty, godziny, ułamki i przedziały zapisane jako pary.
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.
Rozpakowywanie i plansza
auto [a, b], pary w parach jako trójki i kierunki ruchu po planszy.
Sortowanie i olimpiada
Sortowanie par jedną linijką, ranking, przedziały i zdarzenia.
(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:
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";
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";
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; // 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";
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>.
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.
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";
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.
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";
pair<int, string> p = {"Ola", 95}; // BŁĄD: najpierw int, potem string!
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.
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";
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.
pair<int, int> p;
cin >> p.first >> p.second;
cout << "(" << p.first << ", " << p.second << ")\n";
cout << p.first << ":" << p.second << "\n";
pair<int, int> p = {4, 9};
cout << p << "\n"; // BŁĄD: cout nie umie wypisać pary
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.
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";
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";
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.
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";
| po linijce | p.first | p.second |
|---|---|---|
p = {4, 10} | 4 | 10 |
p.first++ | 5 | 10 |
p.second -= p.first | 5 | 5 |
p.first *= 3 | 15 | 5 |
p = {p.second, p.first} | 5 | 15 |
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.
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ź”.
pair<int, int> p = {4, 9};
cout << p.second << p.first;
Pokaż odpowiedź
second (9), zaraz za nim first (4) — bez spacji.pair<int, int> p;
p.first = 5;
cout << p.first + p.second;
Pokaż odpowiedź
p.second to 0. 5 + 0 = 5.pair<string, int> p = {"Ala", 3};
p.second *= 2;
cout << p.first << p.second;
Pokaż odpowiedź
second podwaja się do 6, a first zostaje „Ala”.pair<int, int> a = {1, 2};
pair<int, int> b = a;
b.first = 7;
cout << a.first << b.first;
Pokaż odpowiedź
b to osobna kopia — zmiana b.first nie rusza a.first.pair<int, int> p = {3, 8};
swap(p.first, p.second);
cout << p.first << " " << p.second;
Pokaż odpowiedź
swap zamienia wartości przegródek miejscami.pair<int, int> a = {2, 5}, b = {2, 5};
cout << (a == b) << (a != b);
Pokaż odpowiedź
== daje 1, a != daje 0.pair<char, int> p = {'x', 3};
cout << string(p.second, p.first);
Pokaż odpowiedź
string(3, 'x') to napis z trzech liter x — przepis znasz z lekcji o napisach.pair<int, int> p = make_pair(6, 1);
p = {p.second, p.first};
cout << p.first << p.second;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
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";
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";
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.
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";
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";
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.
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";
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.
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";
}
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(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.
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ź”.
pair<int, int> a = {1, 5}, b = {4, 1};
cout << abs(a.first - b.first) + abs(a.second - b.second);
Pokaż odpowiedź
cout << abs(-7) << abs(3);
Pokaż odpowiedź
abs usuwa minus: 7, a 3 zostaje 3. Wypisane bez spacji.pair<int, int> t = {9, 50};
int m = t.first * 60 + t.second + 20;
cout << m / 60 << ":" << m % 60;
Pokaż odpowiedź
cout << max(3, 8) << min(3, 8);
Pokaż odpowiedź
max daje większą liczbę (8), min — mniejszą (3).pair<int, int> a = {1, 4}, b = {3, 9};
cout << max(a.first, b.first) << " " << min(a.second, b.second);
Pokaż odpowiedź
pair<int, int> x = {2, 3}, y = {1, 4};
cout << x.first * y.second + y.first * x.second << "/" << x.second * y.second;
Pokaż odpowiedź
pair<int, int> p = {0, 0};
p.first += 3;
p.second -= 2;
p.first -= 1;
cout << p.first << "," << p.second;
Pokaż odpowiedź
pair<int, int> a = {3, 6};
int x = 6;
cout << (a.first <= x && x <= a.second);
Pokaż odpowiedź
<=.8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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ą.
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”
| porównanie | first | second | wynik |
|---|---|---|---|
(1, 9) < (2, 0) | 1 < 2 | nie patrzymy | prawda |
(1, 5) < (1, 9) | 1 = 1 | 5 < 9 | prawda |
(2, 0) < (1, 9) | 2 > 1 | nie patrzymy | fałsz |
(1, 9) == (1, 9) | 1 = 1 | 9 = 9 | prawda |
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.
<, >, <=, >=, ==, !=. 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!
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";
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?
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";
}
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.
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";
}
| chcesz | w 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.
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
(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.
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";
| krok | a | b | c |
|---|---|---|---|
| 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.
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ź”.
pair<int, int> a = {2, 1}, b = {1, 9};
cout << (a < b);
Pokaż odpowiedź
a < b to fałsz.pair<int, int> a = {4, 3}, b = {4, 8};
cout << (a < b) << (a == b);
Pokaż odpowiedź
pair<int, int> a = {5, 5};
cout << (a <= a) << (a < a);
Pokaż odpowiedź
pair<string, int> a = {"kot", 1}, b = {"kotek", 0};
cout << (a < b);
Pokaż odpowiedź
pair<int, int> p = max(make_pair(1, 50), make_pair(2, 0));
cout << p.second;
Pokaż odpowiedź
pair<int, int> a = {7, -10}, b = {7, -12};
cout << (a > b);
Pokaż odpowiedź
pair<int, int> t1 = {12, 59}, t2 = {13, 0};
cout << (t1 < t2);
Pokaż odpowiedź
pair<int, int> a = {3, 4}, b = {3, 4};
cout << (a < b) << (a > b) << (a == b);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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}};
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";
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.
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";
}
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";
}
}
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.
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";
}
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.
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";
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?
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";
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.
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ź”.
pair<int, int> t[3] = {{1, 2}, {3, 4}, {5, 6}};
cout << t[1].second + t[2].first;
Pokaż odpowiedź
t[1].second to 4, t[2].first to 5. Razem 9.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ź
t[0] to teraz (5, 6), a t[2] — (1, 2).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ź
pair<int, int> t[3];
cout << t[2].first + t[1].second;
Pokaż odpowiedź
main.pair<string, int> u[2] = {{"Ola", 5}, {"Jan", 7}};
cout << u[1].first[0] << u[0].second;
Pokaż odpowiedź
u[1].first to napis „Jan”, a jego znak 0 to J. u[0].second to 5.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ź
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ź
first: t[2] to teraz (6, 3).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ź
t[0] i t[1] są równe: (4, 1) i (4, 1).8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
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
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.
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";
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.
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";
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";
}
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>> 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";
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.
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";
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.
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.
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ź”.
pair<int, int> p = {5, 2};
auto [a, b] = p;
a++;
cout << a << p.first;
Pokaż odpowiedź
a to kopia — zwiększa się tylko ona. p.first zostaje 5.pair<int, int> p = {5, 2};
auto &[a, b] = p;
a++;
cout << p.first << b;
Pokaż odpowiedź
& zmienna a to druga nazwa p.first, więc p.first zmienia się na 6.pair<int, pair<int, int>> q = {1, {2, 3}};
cout << q.second.first + q.first;
Pokaż odpowiedź
q.second to para (2, 3), jej first to 2. Plus q.first (1) daje 3.pair<int, pair<int, int>> a = {1, {5, 0}}, b = {1, {4, 9}};
cout << (a < b);
Pokaż odpowiedź
pair<int, int> t[2] = {{1, 2}, {3, 4}};
int s = 0;
for (auto [x, y] : t) s += x * y;
cout << s;
Pokaż odpowiedź
pair<int, int> t[2] = {{1, 2}, {3, 4}};
for (auto [x, y] : t) x = 0;
cout << t[0].first;
Pokaż odpowiedź
& zerujemy kopie, a tablica zostaje bez zmian.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ź
& zamieniamy prawdziwe przegródki: t[1] to teraz (4, 3).pair<int, pair<int, int>> d = {2024, {2, 29}};
cout << d.second.second << "/" << d.second.first;
Pokaż odpowiedź
d.second to (2, 29): miesiąc 2 i dzień 29.8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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:
// 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
| litera | kierunek | numer | krok (dw, dk) |
|---|---|---|---|
| G | góra | 0 | (-1, 0) |
| P | prawo | 1 | (0, 1) |
| D | dół | 2 | (1, 0) |
| L | lewo | 3 | (0, -1) |
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.
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";
| polecenie | krok | pozycja |
|---|---|---|
| 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.
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";
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)?
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";
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.
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";
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.
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";
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.
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ź”.
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ź
ruch[3] to krok w lewo (0, −1): wiersz się nie zmienia, kolumna maleje do 1.string kierunki = "GPDL";
cout << kierunki.find('D');
Pokaż odpowiedź
int d = 0;
d = (d + 3) % 4;
d = (d + 3) % 4;
cout << d;
Pokaż odpowiedź
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ź
int n = 3;
pair<int, int> p = {0, 2};
int nw = p.first - 1;
cout << (nw >= 0 && nw < n);
Pokaż odpowiedź
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ź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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.
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";
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.
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";
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.
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";
}
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";
}
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.
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.
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";
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.
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";
}
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].
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ź”.
int a[5] = {4, 1, 3, 1, 2};
sort(a, a + 5);
cout << a[0] << a[4];
Pokaż odpowiedź
pair<int, int> t[3] = {{2, 1}, {1, 9}, {2, 0}};
sort(t, t + 3);
cout << t[1].first << t[1].second;
Pokaż odpowiedź
string s[3] = {"kot", "Kot", "ala"};
sort(s, s + 3);
cout << s[0];
Pokaż odpowiedź
int a[5] = {5, 4, 3, 2, 1};
sort(a, a + 3);
cout << a[0] << a[3];
Pokaż odpowiedź
pair<int, string> t[2] = {{-5, "Ola"}, {-7, "Jan"}};
sort(t, t + 2);
cout << t[0].second;
Pokaż odpowiedź
pair<int, int> t[3] = {{7, 1}, {5, 2}, {7, 3}};
sort(t, t + 3);
cout << t[2].second;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
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).
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
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.
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";
| zdarzenie | teraz | najwięcej |
|---|---|---|
| (1, +1) | 1 | 1 |
| (2, +1) | 2 | 2 |
| (5, −1) | 1 | 2 |
| (5, +1) | 2 | 2 |
| (6, −1) | 1 | 2 |
| (8, −1) | 0 | 2 |
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.
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";
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).
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";
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.
| n | każdy z każdym (n² / 2) | sort (n · log₂n) |
|---|---|---|
| 1 000 | 500 000 — błyskawicznie | około 10 000 |
| 100 000 | 5 000 000 000 — kilkanaście sekund | około 1 700 000 — ułamek sekundy |
| 1 000 000 | 500 000 000 000 — godziny | około 20 000 000 — ułamek sekundy |
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.
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ź”.
pair<int, int> a = {1, 5}, b = {4, 9};
cout << (b.first <= a.second);
Pokaż odpowiedź
pair<int, int> wyjscie = {5, -1}, wejscie = {5, 1};
cout << (wyjscie < wejscie);
Pokaż odpowiedź
pair<int, int> w[3] = {{4, 1}, {6, 0}, {5, 3}};
sort(w, w + 3);
cout << w[1].second;
Pokaż odpowiedź
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ź
max.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ź
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ź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: 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.
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.
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.
Ś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.
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.