Bolek oznajmia Alinie sam wynik, po czym ona zawsze potrafi zgadnąć, jakie liczby wypadły na kostkach. W jaki sposób? Tym nie będziemy się tutaj zajmować – nie chcemy Ci psuć zabawy z rozwiązywania zagadki. W zamian za to napiszemy program, który działa zgodnie z procedurą wykonywaną przez Bolka. Wykorzystamy w nim jedną zmienną pomocniczą \(w\), do której zastosujemy przypisania opisane w zagadce.

#include <iostream>
using namespace std;

int main() {
    int kostka1, kostka2, kostka3;
    cin >> kostka1 >> kostka2 >> kostka3;
    int w = kostka1;
    w = w * 2;
    w = w + 5;
    w = w * 5;
    w = w + kostka2;
    w = w * 10;
    w = w + kostka3;
    cout << w << endl;
}

Powyższy program moglibyśmy też napisać tak:

#include <iostream>
using namespace std;

int main() {
    int kostka1, kostka2, kostka3;
    cin >> kostka1 >> kostka2 >> kostka3;
    int w1 = kostka1;
    int w2 = w1 * 2;
    int w3 = w2 + 5;
    int w4 = w3 * 5;
    int w5 = w4 + kostka2;
    int w6 = w5 * 10;
    int w7 = w6 + kostka3;
    cout << w7 << endl;
}

Skrócone instrukcje przypisania

a = a + b;
a = a - b;
a = a * b;
a = a / b;
a = a % b;

a += b;
a -= b;
a *= b;
a /= b;
a %= b;

#include <iostream>
using namespace std;

int main() {
    int kostka1, kostka2, kostka3;
    cin >> kostka1 >> kostka2 >> kostka3;
    int w = kostka1;
    w *= 2;
    w += 5;
    w *= 5;
    w += kostka2;
    w *= 10;
    w += kostka3;
    cout << w << endl;
}

a++; // to samo co: a += 1;
a--; // to samo co: a -= 1;

A oto inny przykład. Zobaczymy, jak zastosowanie instrukcji przypisania może uprościć rozwiązanie zadania Czas z drugiej lekcji. Przypomnijmy, że należało w nim przeliczyć czas \(t\) sekund na zapis w godzinach, minutach i sekundach.

To zadanie można oczywiście rozwiązać bez użycia instrukcji przypisania, jednak z jej pomocą rozwiązanie staje się bardziej przejrzyste. Klucz do rozwiązania stanowi wprowadzenie trzech zmiennych: \(g\), \(m\) i \(s\), które oznaczają odpowiednie fragmenty wyniku: liczbę pełnych godzin w czasie \(t\), liczbę pełnych minut w tym czasie z wyłączeniem pełnych godzin i pozostałą liczbę sekund. Wartości tych zmiennych możemy obliczać w kolejności \(g\), \(m\), \(s\) lub odwrotnie. W poniższym programie obraliśmy właśnie kolejność odwrotną, natomiast rozwiązanie wybierające kolejność zgodną z podaną pozostawiamy już uczestnikom kursu.

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    int g, m, s;
    s = t % 60;
    t /= 60;
    m = t % 60;
    t /= 60;
    g = t;
    cout << g << "g" << m << "m" << s << "s" << endl;
}

Zakładając, że w automacie dostępnych jest dowolnie wiele puszek naszego ulubionego napoju, chcielibyśmy wiedzieć, ile puszek możemy kupić za pomocą monet, które aktualnie mamy w kieszeni. Napiszemy program, który wczyta liczby poszczególnych typów monet, które mamy, i wypisze liczbę puszek, które chcemy kupić.

Myślenie nad rozwiązaniem warto rozpocząć od rozważenia wszystkich możliwych układów dających łącznie 6 zł. Są to:

6 = 5 + 1
6 = 2 + 2 + 2
6 = 2 + 2 + 1 + 1
6 = 2 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 1 + 1

Zauważmy, że w ogóle najbardziej opłaca nam się używać układu 5+1. Jest to jedyny układ, w którym występuje moneta pięciozłotowa, więc jeśli którejś monety o tym nominale nie zużyjemy w ten sposób, to nie wykorzystamy jej już wcale. Co więcej, jest to jedyny układ używający tylko jednej złotówki. Gdyby nam miała zostać na końcu jakaś pięciozłotówka, a którąś jednozłotówkę wykorzystalibyśmy w innym układzie, moglibyśmy wyjąć ją z tego innego układu i stworzyć z tych dwóch monet układ 5+1. W ten sposób liczba stworzonych układów, czyli liczba kupionych puszek, na pewno by nie zmalała. Kontynuując to postępowanie, możemy uzasadnić, że rzeczywiście opłaca nam się stworzyć możliwie wiele układów 5+1.

Dalej możemy uzasadnić podobnie, że kolejnym najbardziej opłacalnym układem jest 2+2+2. Jeśli mamy układ z monetami dwu- i jednozłotowymi i odpowiednio wiele dwuzłotówek poza nim, możemy podmienić jednozłotówki z układu na te dwuzłotówki, otrzymując układ 2+2+2. Wtedy kupujemy puszkę, zużywając te dwuzłotówki, i kontynuujemy to podejście, aż zostanie nam łącznie mniej niż trzy dwuzłotówki. Nietrudno zobaczyć, że możemy je wszystkie umieścić w jednym układzie typu 2+2+1+1 lub 2+1+1+1+1, jeśli oczywiście wystarczy nam jednozłotówek, a pozostałe jednozłotówki wrzucać już do automatu po sześć.

Opisane pomysły możemy zapisać w postaci pierwszego rozwiązania. Użyjemy w nim zmiennej pomocniczej \(wynik\), w której zapamiętamy liczbę już zakupionych puszek.

#include <iostream>
using namespace std;

int main() {
    int n1, n2, n5;
    cin >> n1 >> n2 >> n5;
    int wynik = 0;

    /* 6 = 5 + 1 */
    if (n5 >= n1) {
        wynik += n1;
        n5 -= n1;
        n1 = 0;
    } else {
        // Pamietaj o zaktualizowaniu wszystkich zmiennych!
        wynik += n5;
        n1 -= n5;
        n5 = 0;
    }

    /* 6 = 2 + 2 + 2 */
    wynik += n2 / 3;
    n2 %= 3;

    /* 6 = 2 + 2 + 1 + 1
       6 = 2 + 1 + 1 + 1 + 1 */
    if (n2 >= 1 && 2 * n2 + n1 >= 6) {
        // Pamietaj o zaktualizowaniu wszystkich zmiennych!
        wynik++;
        n1 -= 6 - 2 * n2;
        n2 = 0;
    }

    /* 6 = 1 + 1 + 1 + 1 + 1 + 1 */
    wynik += n1 / 6;
    n1 %= 6;

    cout << wynik << endl;
}

Zacznijmy od początku rozwiązania. Liczba układów 5+1, które jesteśmy w stanie stworzyć, jest równa \(\min(n1,n5)\). Okazuje się, że w języku C++ dostępne są funkcje min i max. Aby mieć do nich dostęp, należy na początku programu dopisać jeden dodatkowy wiersz, w którym zadeklarujemy chęć używania podstawowych algorytmów w języku C++:

#include <iostream>
#include <algorithm>
using namespace std;

To pozwoli nam uprościć część rozwiązania dotyczącą przypadku 5+1. A co z pozostałymi przypadkami? Okazuje się, że z nimi będzie jeszcze prościej. Wyobraźmy sobie, że wszystkie monety dwu- i jednozłotowe, jakie pozostały nam po rozważaniu przypadku 5+1, ustawiliśmy w rzędzie – najpierw dwuzłotówki, a potem jednozłotówki. Jeśli będziemy je wrzucać do automatu w tym porządku, zakupimy dokładnie

(2 * n2 + n1) / 6;

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n1, n2, n5;
    cin >> n1 >> n2 >> n5;

    /* 6 = 5 + 1 */
    int wynik = min(n1, n5);
    n1 -= wynik;

    /* pozostale */
    wynik += (2 * n2 + n1) / 6;

    cout << wynik << endl;
}

Nie jest jasne, w jaki sposób prostokąty są zadane. Czy są np. narysowane na kartce? W jaki sposób wprowadzić zawartość kartki do komputera? Zeskanować? Jak stwierdzić na przykład, że jakiś konkretny punkt leży wewnątrz prostokąta? Jeżeli zaczniemy się przyglądać punktowi narysowanemu bardzo blisko brzegu za pomocą mikroskopu, to odkryjemy, że to nie żaden punkt, tylko olbrzymie nieregularne rozlewiska tuszu na górzystej przestrzeni papieru.

Francuski uczony René Descartes (znany jako Kartezjusz) zaproponował metodę opisu obiektów geometrycznych za pomocą ciągów liczb, wprowadzając w tym celu prostokątny układ współrzędnych, zwany też układem współrzędnych kartezjańskich. W układzie kartezjańskim punkt opisać można za pomocą dwóch liczb, a np. trójkąt za pomocą trzech punktów (czyli sześciu liczb). Dzisiaj wszyscy uczymy się tej metody w szkole.

Załóżmy, że autorowi zadania chodziło o to, że prostokąty są zadane właśnie za pomocą współrzędnych kartezjańskich. Na to wskazywałoby sformułowanie "osie układu współrzędnych" pojawiające się w treści zadania. Dość oczywiste jest, że punkt \(A\) możemy teraz opisać za pomocą dwóch liczb \(Ax\) i \(Ay\) będących odpowiednio współrzędnymi \(x\) i \(y\) punktu \(A\) w kartezjańskim układzie współrzędnych. Wciąż jednak nie jest jasne, jaki wariant opisu prostokątów autor zadania miał na myśli. Dla przykładu, prostokąt może być zadany jako:

• cztery wierzchołki w dowolnej kolejności,
• dwa przeciwległe wierzchołki w dowolnej kolejności,
• dolny lewy wierzchołek, długość boku równoległego do osi X, długość boku równoległego do osi Y,
• górny lewy wierzchołek i dolny prawy wierzchołek,
• dolny lewy wierzchołek i górny prawy wierzchołek.

Po chwili namysłu pojawiają się nam kolejne pytania:

• Czy prostokąt składa się z brzegu i wnętrza, samego brzegu, czy też samego wnętrza?
• Czy w reprezentacji prostokąta występują liczby całkowite, wymierne, rzeczywiste?

Analizę naszego zadania zacznijmy od przypomnienia sobie, jaka jest część wspólna dwóch prostokątów. Niech \(R\) będzie częścią wspólną prostokątów \(P\) i \(Q\). Prostokąty \(P\), \(Q\) i \(R\) (a skąd wiadomo, że \(R\) jest prostokątem?) to zbiory punktów. Zastanówmy się, kiedy punkt \(A\) należy do \(R\). Zgodnie z definicją:

punkt \(A\) należy do \(R\), przecięcia prostokątów \(P\) i \(Q\), wtedy i tylko wtedy, gdy należy zarówno do prostokąta \(P\), jak i prostokąta \(Q\).

Spróbujmy sformułować jakieś łatwe kryterium na to, kiedy punkt \(A\) należy do prostokąta \(P\) (podobnie do prostokąta \(Q\)). W tym celu przyjrzyjmy się dwóm przeciwległym wierzchołkom prostokąta \(P\) – lewemu dolnemu i prawemu górnemu. Oznaczmy ich współrzędne odpowiednio przez \((a,b)\) i \((c,d)\). Zauważmy, że mamy

\(a < c\) oraz \(b < d\).

Nietrudno teraz zauważyć, że każdy punkt należący do prostokąta \(P\) (pamiętajmy, że do prostokąta nie zaliczamy jego brzegu) musi mieć współrzędną \(x\) z przedziału otwartego \((a,c)\), a współrzędną \(y\) z przedziału \((b,d)\). Zatem punkt \(A=(s,t)\) należy do prostokąta \(P\) wtedy i tylko wtedy, gdy \(a < s < c\) oraz \(b < t < d\). Podobnie dla prostokąta \(Q\) o wierzchołkach \((e,f)\) i \((k,l)\) mamy, że punkt \(A\) należy do prostokąta \(Q\) wtedy i tylko wtedy, gdy \(e < s < k\) oraz \(f < t < l\). Z tego wynika, że punkt \(A\) należy do przecięcia \(R\) prostokątów \(P\) i \(Q\), gdy \(s\) należy do części wspólnej przedziałów \((a,c)\) i \((e,k)\), natomiast \(t\) należy do części wspólnej przedziałów \((b,d)\) i \((f,l)\).

W ten sposób nasze zadanie wyznaczenia przecięcia dwóch prostokątów sprowadziliśmy do dużo prostszego zadania obliczenia części wspólnej dwóch otwartych przedziałów liczbowych zadanych przez ich końce. Co jest zatem częścią wspólną dwóch przedziałów liczbowych \((x_1,y_1)\) i \((x_2,y_2)\), przy czym wiemy, że \(x_1 < y_1\) i \(x_2 < y_2\)? Nietrudno zauważyć, że każda liczba \(z\), dla której \(x_1 < z < y_1\) oraz \(x_2 < z < y_2\), musi spełniać: \(\max(x_1,x_2) < z\) oraz \(z < \min(y_1,y_2)\). Rozważmy kilka przykładów:

• \((x_1,y_1) = (5,10)\), \((x_2,y_2) = (7,12)\)
  \(\max(x_1,x_2) = 7\), \(\min(y_1,y_2) = 10\) i częścią wspólną przedziałów \((x_1,y_1)\) i \((x_2,y_2)\) jest \((7,10)\)
• \((x_1,y_1) = (5,10)\), \((x_2,y_2) = (3,15)\)
  \(\max(x_1,x_2) = 5\), \(\min(y_2,y_2) = 10\) i częścią wspólną przedziałów \((x_1,y_1)\) i \((x_2,y_2)\) jest \((5,10)\)
• \((x_1,y_1) = (5,10)\), \((x_2,y_2) = (12,15)\)
  \(\max(x_1,x_2) = 12\), \(\min(y_1,y_2) = 10\) i częścią wspólną przedziałów \((x_1,y_1)\) i \((x_2,y_2)\) jest \((12,10)\); jeśli przyjmiemy, że gdy lewy koniec przedziału otwartego jest nie mniejszy od jego prawego końca, to oznacza to przedział pusty, wówczas i w tym przypadku dostajemy poprawne rozwiązanie.