Pewnie zastanawiacie się jakie zadanie dzisiaj rozwiążemy. A takie rozwiążemy:
Zadanie 5: Wieża z klocków
Tomek ułożył wieżę z klocków. Na każdym klocku znajduje się pewna cyfra. Tomek sprawdza jaką liczbę ułożył czytając cyfry od góry do dołu. Ale co to? Czyżby Tomek się pomylił? Tomkowi bardzo zależało na tym, aby liczba która powstanie, była parzysta. Teraz Tomek ma kłopot, bo nie chce ustawiać wszystkich klocków od nowa. Wymyślił, że oszuka to w następujący sposób. Weźmie któryś z klocków i wszystkie klocki powyżej. Następnie bardzo ostrożnie odwróci je i odłoży z powrotem. Dla przykładu jeśli liczba którą Tomek ułożył to 123456 i Tomek weźmie klocek 4 to po operacji otrzyma on liczbę 432156 (zwróć uwagę na to że liczba Tomka od początku była już parzysta, Tomek nie jest bystry jeśli chodzi o duże liczby).
Wejście
Na wejściu znajduje się jedna liczba n (1 ≤ n ≤ 1018). Oznacza ona liczbę, którą Tomek otrzymał z wieży klocków.
Wyjście
Na wyjściu należy wypisać jedną liczbę całkowitą – minimalną liczbę operacji jaką musi wykonać Tomek, aby uzyskać liczbę parzystą. Jeśli uzyskanie liczby parzystej nie jest możliwe, należy wypisać -1.
Przykład
Dla danych wejściowych:
12345Poprawną odpowiedzią jest:
2Dla danych wejściowych:
123456Poprawną odpowiedzią jest:
0Wytłumaczenie do przykładów: W pierwszym przykładzie możemy podnieść klocek 4, otrzymując po tej operacji liczbę 43215. Następnie możemy podnieść klocek 5 otrzymując 51234. Można udowodnić, że nie można uzyskać liczby parzystej mniejszą liczbą ruchów. W drugim przypadku liczba jest już parzysta, więc minimalna ilość operacji to zero.
W dzisiejszej notce mowa będzie o systemach liczbowych. Jeden system liczbowy powinieneś już znać. To system dziesiętny. Używamy w nim 10 cyfr: 0, 1, 2, 3, 4, 5, 6, 7, 8 oraz 9. Cyfry układamy w ciąg niczym Tomek układający klockami. I tak trzy cyfry ustawione obok siebie w ciąg 1, 2, 3 oznaczają liczbę 123 (tak, mam świadomość, że piszę tu rzeczy, które są dla wszystkich oczywiste – ale taki jest właśnie zamysł tego wpisu). Możemy to rozumieć inaczej. 1 to liczba setek, 2 to liczba dziesiątek, a 3 to liczba jedności. Czyli nasza liczba przedstawia się jako 1 x 100 + 2 x 10 + 3 x 1, albo inaczej: 1 x 102 + 2 x 101 + 3 x 100.
Myk polega na tym, że liczbę 10 (którą nazywamy bazą systemu liczbowego) możemy zastąpić dowolną liczbą naturalną, większą od jedynki (od biedy można zdefiniować system “jedynkowy”; stwarza on jednak więcej problemów, którymi nie mamy dziś siły się zajmować). Weźmy dla przykładu dwójkę. Używać będziemy w niej 2 cyfr: 0 oraz 1. Cyfry te będziemy układać w ciąg. I tak ustawienie obok siebie cyfr 101 będzie oznaczało liczbę 1 x 22 + 0 x 21 + 1 x 20 = 5. Jest to tak zwany system binarny, który ma kluczową rolę w systemach komputerowych.
Oczywiście, możemy użyć innej liczby. Dla przykładu w systemie trójkowym używamy 3 cyfr: 0, 1 oraz 2, natomiast 210 oznacza wtedy 2 x 32 + 1 x 31 + 0 x 30 = 21.
Często przy liczbach zapisanych w różnych systemach liczbowych używa się indeksu dolnego do zaznaczenia w jakim systemie liczbowym zapisana jest dana liczba. Wtedy zapis 210(3) = 21(10) ma sens (210 w zapisie trójkowym to 21 w zapisie dziesiętnym). 210 = 21 wyglądałoby trochę dziwnie.
Weźmy na warsztat inny ważny system liczbowy: system szesnastkowy. Używamy w nim 16 cyfr… i tu pojawia się problem. Bo cyfr mamy tylko 10. Ale to nic.. użyjemy liter. Więc jeszcze raz: używamy w nim 16 cyfr: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E oraz F, przy czym cyfra A reprezentuje 10, B reprezentuje 11 i tak dalej. Dla przykładu 7B(16) oznacza 7 x 161 + 11 x 160 = 123(10).
Na matematyce być może słyszałeś, że mnożenie/dzielenie przez 10 “przesuwa przecinek”. W informatyce jest nieco inaczej. Gdyż pamiętaj, że “nasze” dzielenie jest całkowitoliczbowe. Zatem wszystko co znajdzie się za przecinkiem – znika. W takiej sytuacji dzieląc dowolną liczbę przez 10 (100, 1000…) usuwamy jej ostatnią (dwie ostatnie, trzy ostatnie…) cyfrę. Na przykład 12345 / 10 = 1234. Aby zobaczyć co to była za cyfra (dwie ostatnie cyfry, trzy ostatnie cyfry), możemy policzyć resztę z dzielenia tej liczby przez 10 (100, 1000). Na przykład 12345 % 10 = 5.
Taka sprytna sztuczka jest możliwa dlatego, że kolejna potęga 10 jest 10-tą wielokrotnością poprzedniej. To znaczy: 1000 = 100 x 10. Ach kocham tłumaczyć te oczywiste oczywistości 🙂 Ludzie zawsze patrzą na mnie jak na wariata 🙂 To do czego dążę, to to, że z analogiczną sytuacją mamy w każdym systemie liczbowym. Niech x1, x2, x3, x4 będą dowolnymi cyframi w systemie b-tkowym. Wtedy x1x2x3x4(b) / b2 = (x1 x b3 + x2 x b2 + x3 x b1 + x4 x b0) / b2 = x1 x b3 / b2 + x2 x b2 / b2 + x3 x b1 / b2 + x4 x b0 / b2 = x1 x b1 + x2 x b0 + 0 + 0 = x1x2(b). Zatem dzieląc w dowolnym systemie liczbowym, liczbę przez bk (gdzie b to tak zwana podstawa systemu liczbowego), usuwamy z liczby k ostatnich cyfr.
Ma to ogromne zastosowanie w programowaniu. Po pierwsze, możemy łatwo wypisać wszystkie cyfry danej liczby:
#include <iostream>
using namespace std;
int main()
{
int liczba;
cout << "Podaj liczbę: ";
cin >> liczba;
cout << "Cyfry liczby " << liczba << " to: ";
while (liczba > 0)
{
cout << liczba % 10 << " ";
liczba /= 10;
}
cout << endl;
return 0;
}Przykładowe uruchomienie programu może wyglądać następująco:
Podaj liczbę: 32766
Cyfry liczby 32766 to: 6 6 7 2 3Ponieważ pętlę while poznaliśmy dopiero co, prześledźmy działanie programu na tym przykładzie. Najpierw deklarujemy zmienną o nazwie liczba. Następnie wyświetlamy na ekranie napis “Podaj liczbę: ” i czekamy aż użytkownik wpisze liczbę. Załóżmy, że wpisał 32766. Wyświetlamy na ekranie napis “Cyfry liczby 32766 to: “. Następnie sprawdzamy czy liczba jest większa od zera. Jest, zatem wyświetlamy resztę z dzielenia liczby 32766 przez 10, czyli 6 i dodatkowo wyświetlamy za nią znak spacji. Następnie dzielimy liczbę 32766 przez 10. Naszą liczbą jest teraz 3276. Sprawdzamy czy jest ona większa od zera. Jest, zatem wyświetlamy resztę z dzielenia jej przez 10 (6) i dzielimy ją przez 10. Naszą liczbą jest teraz 327. Jest ona większa od zera, więc wyświetlamy resztę z dzielenia przez 10 (7) i dzielimy ją przez 10. Naszą liczbą jest teraz 32. Jest ona większa od zera, wyświetlamy resztę z dzielenia przez 10 (2) i dzielimy ją przez 10. Naszą liczbą jest teraz 3. Jest ona większa od zera, wyświetlamy resztę z dzielenia przez 10 (3) i dzielimy ją przez 10. Naszą liczbą jest teraz 0. 0 nie jest większe od zera, zatem kończymy pętlę while, wyświetlamy znak nowej linii i kończymy program.
Zwróć uwagę, że cyfry zostały podane w odwrotnej kolejności. Na razie musi nam to wystarczyć. Z problemem poradzimy sobie dopiero gdy poznamy tablice.
Ciekawszym(?) zastosowaniem naszego wzoru, jest przeliczenie liczby z systemu dziesiętnego na dowolny inny system liczbowy. Robi to następujący program:
#include <iostream>
using namespace std;
int main()
{
int liczba;
int system;
cout << "Podaj liczbę: ";
cin >> liczba;
cout << "Podaj system: ";
cin >> system;
cout << "Liczba " << liczba << " zapisana w systemie to: ";
while (liczba > 0)
{
cout << liczba % system << " ";
liczba /= system;
}
cout << endl;
return 0;
}Program działa analogicznie do poprzedniego. Tym razem jednak dzielimy i wypisujemy resztę z dzielenia przez zmienną system. Przykładowe uruchomienie programu może wyglądać następująco:
Podaj liczbę: 10
Podaj system: 2
Liczba 10 zapisana w systemie to: 0 1 0 1I faktycznie 10(10) = 1010(2). Pamiętaj że program wypisał cyfry w odwrotnej kolejności. Jak się okaże później, ta kolejność dla komputerów jest po prostu bardziej naturalna.
Wiedząc już czym jest system binarny i jak przeliczać z systemu dziesiętnego na system binarny, możemy przejść do tego w jaki sposób są one pamiętane w C++. Komputery reprezentują liczby w systemie dwójkowym, gdyż wtedy łatwo jest im je reprezentować za pomocą sygnałów: zero: prąd nie płynie; jeden: prąd płynie. Ponadto, zawczasu, wszystkie zmienne mają ustaloną wielkość, w bitach. I tak zmienna int jest wartością 32 bitową*. Oznacza to, że każda taka zmienna, reprezentuje ciąg złożony z 32 cyfr (zer i jedynek). Zatem liczba 32766 jest zapisywana jako 00000000000000000000011111100110. Jak widzicie pojawia się pewien problem. Choć ten ciąg znaków jest prosty i naturalny dla komputera. To jest uciążliwy dla nas…. bo jest za długi. Z pomocą przychodzi nam system szesnastkowy. Ponieważ 16 jest wielokrotnością 2, wystarczy podzielić powyższą liczbę na bloki o długości 4 (bo 16 = 24): 0000 0000 0000 0000 0000 0111 1110 0110 a następnie pozamieniać poszczególny blok na cyfrę w systemie szesnastkowym: 000007E6. Zwróć uwagę, że 1110 to w dziesiętnym 14, a 14 to E w systemie 16-stkowym, dlatego też E pojawiło się w naszej liczbie.
Systemu binarnego, ósemkowego i szesnastkowego, możemy używać w języku C++:
#include <iostream>
using namespace std;
int main()
{
int a = 0b11111100110;
int b = 03746;
int c = 0x7E6;
cout << a << " " << b << " " << c << endl;
return 0;
}Liczby w systemie szesnastkowym powinniśmy poprzedzić symbolami 0x, w systemie binarnym użyjemy 0b a w systemie ósemkowym 0 (systemu ósemkowego rzadko będziemy używać; wydaje mi się, że był on używany zamiast szesnastkowego bo ktoś się nie zorientował, że w systemie szesnastkowym możemy używać liter w miejsce brakujących cyfr).
Zastanówmy się teraz, jak zapamiętywać w komputerze liczby ujemne. Prostym pomysłem, jaki prawie wszystkim przychodzi do głowy, jest poświęcenie jednego bitu na znak (jeśli wam też taki pomysł przyszedł do głowy, to gratuluję! Właśnie wymyśliliście zapis znak-moduł). Jest to świetny pomysł, zaczerpnięty z tego w jaki my zapisujemy liczby w systemie dziesiętnym. Jeśli liczba jest ujemna, wstawiamy znak “-” przed nią, a jeśli jest dodatnia to znak “+” (który później jest pomijany dla naszej wygody). I faktycznie w naszym systemie dziesiętnym to jest bardzo dobry pomysł, aby w ten sposób zapisywać liczby. A to dlatego, że nasze liczby mogą być dowolnie długie. Ponieważ jednak w komputerach liczby typu int są 32-bitowe*, istnieje lepszy pomysł. Mianowicie najwyższy bit jest brany z minusem. Łatwo zrozumieć to na przykładzie 4-bitowym. Wtedy b1b2b3b4 oznaczałoby b1 x (-23) + b2 x 22 + b3 x 21 + b3 x 20. Dla przykładu 1010(2) oznaczało by 1 x (-8) + 0 x 4 + 1 x 2 + 0 x 1 = -8 + 2 = -6.
System ten nazywa się zapisem uzupełnień do dwóch (U2). Są dwa powody dla których uważany jest on za lepszy od zapisu znak-moduł. Pierwszy z nich to taki, że w zapisie znak-moduł liczba 0 ma dwie reprezentacje: +0 i -0. Jest to w mojej opinii bardzo słaby powód. Drugi powód jest już dużo poważniejszy. Niestety, omówimy go dokładniej innym razem (ta notka i tak jest już za długa). Wiąże się to z tym, że łatwiej jest procesorowi wykonywać operacje na liczbach w takim systemie.
Po tych dywagacjach, możemy w końcu policzyć jak duże liczby możemy zapisać w zmiennej typu int. Przedział tych liczb, które dają się zapisać w danym typie, nazywamy zakresem. Najmniejszą liczbą dającą się tu zapisać to* liczba -2 147 483 648, a liczba największa to 2 147 483 647. I teraz najfajniejsze: nie musicie tej liczby zapamiętywać. Ja pamiętam, że zakres to około ±2 x 109 i mi to w zupełności wystarczy. Jeśli ktoś zapomni, to może skorzystać z następującego programu:
#include <iostream>
#include <limits>
using namespace std;
int main()
{
cout << numeric_limits<int>::max() << endl;
return 0;
}Sam bym z tego kodu korzystał, gdybym umiał zapamiętać tę składnię 😀 Samemu używam takiego programu, który robi to samo*:
#include <iostream>
#include <limits>
using namespace std;
int main()
{
cout << 0x7fffffff << endl;
return 0;
}“7 i siedem f” łatwo mi zapamiętać. A jak jeszcze zrozumiemy, że w zapisie binarnym oznacza to zero i 31 jedynek, to zapamiętać już będzie bardzo łatwo.
Ostatnia już rzecz. W C++ możemy użyć innych typów. Jeśli chcemy użyć zmiennej 8-bitowej*, posłużymy się zmienną char (o innym zastosowaniu zmiennej char, powiemy sobie wkrótce). Zakres tego typu to od -128 do 127. Jeśli chcemy użyć zmiennej 16-bitowej*, użyjemy typu short. Zakres tego typu to od -32 768 do 32 767. 32-bitowy* typ już poznaliśmy – to int. Ostatnim typem jest typ 64-bitowy*: long long. Zakres tego typu to od -9 223 372 036 854 775 808 do 9 223 372 036 854 775 807. Ja zapamiętuję, że to ± coś x 1018 i mi to w zupełności wystarcza. Z typów int oraz long long będziemy korzystać notorycznie. Zmienną typu char będziemy wykorzystywać w innych celach (póki nie poznamy typu string), a short być może w ogóle się nie zdarzy nam korzystać. Oprócz tego, że typy te oczywiście zajmują inną ilość pamięci w komputerze, to również czas operacji na nich jest inny (zwłaszcza mnożenie, dzielenie). Przetestujemy sobie to dokładnie później.
Ufff. Przejdźmy do naszego zadania. Pamiętajmy, że liczba jest parzysta, jeśli jej ostatnia cyfra to 0, 2, 4, 6 lub 8. Są cztery możliwe odpowiedzi:
- -1 jeśli wieża klocków nie zawiera cyfr 0, 2, 4, 6 ani 8.
- 0 jeśli liczba jest już parzysta.
- 1 jeśli pierwsza cyfra to 0, 2, 4, 6 albo 8 (wtedy wystarczy podnieść ostatni klocek i odwrócić całość)
- 2 w przeciwnym przypadku. Bierzemy wtedy dowolny klocek z cyfrą 0, 2, 4, 6 albo 8, odwracamy go w ten sposób, aby klocek ten znalazł się na górze, a następnie podnosimy ostatni klocek i odwracamy całość (przykład 1 w treści zadania)
Dzięki temu, że wiemy jak przejrzeć wszystkie cyfry w naszej liczbie, możemy łatwo rozwiązać to zadanie.
#include <iostream>
using namespace std;
int main()
{
long long n;
bool is_first_even;
bool is_last_even;
bool has_even = false;
cin >> n;
is_last_even = n % 2 == 0;
while (n > 0)
{
int last_digit = n % 10;
if (last_digit % 2 == 0)
{
has_even = true;
}
is_first_even = last_digit % 2 == 0;
n /= 10;
}
if (!has_even)
{
cout << -1 << endl;
}
else if (is_last_even)
{
cout << 0 << endl;
}
else if (is_first_even)
{
cout << 1 << endl;
}
else
{
cout << 2 << endl;
}
return 0;
}Program jest długi, gdyż ma formę edukacyjną i starałem się aby był zrozumiały. Ponieważ n jest duże (sekcja wejście w zadaniu mówi o 1 ≤ n ≤ 1018), musimy użyć typu long long. Następnie definiuję 3 zmienne logiczne. Pierwsza określa czy pierwszy klocek (na górze) jest parzysty, druga czy ostatni klocek jest parzysty, a ostatnia, czy w ogóle jakiś klocek był parzysty. Po wczytaniu zmiennej n, łatwo jest sprawdzić czy ostatni klocek jest parzysty. Jest jeśli cała liczba jest podzielna przez 2, co sprawdzamy licząc resztę z dzielenia przez 2 i sprawdzając czy wynik tej operacji jest zerem. Dalej następuje pętla znana nam już z dzisiejszej notki. Dopóki n jest większe od zera, obliczamy ostatnią cyfrę, licząc resztę z dzielenia n przez 10. Dalej następują dwie instrukcje, do których zaraz wrócimy, a następnie dzielimy n przez 10, przechodząc w ten sposób do następnej cyfry (dokładniej zostało to opisane pod pierwszym programem w tej notce).
Gdy napotkamy klocek, który jest parzysty, zapisujemy wartość true do zmiennej has_even. Początkowo zmienna jest zainicjowana na false. Zatem, jeśli nie napotkamy żadnego klocka parzystego, jej wartość nie ulegnie zmianie i będzie równa false. Natomiast, jeśli napotkamy, zostanie ona zmieniona na true i taka już pozostanie. Zatem po zakończeniu pętli, zmienna has_even ma taką wartość jaką od niej oczekiwaliśmy. Jest równa true wtedy i tylko wtedy gdy któryś z klocków Tomka był parzysty.
Wartość is_first_even jest zmieniana w każdej pojedynczej iteracji pętli. W każdej chwili zmienna ta pamięta, czy ostatni napotkany klocek był parzysty. Dzięki temu, po wyjściu z pętli, zmienna ta będzie pamiętała o ostatnim klocku, czyli o klocku, który na wieży jest najwyżej.
Dalej już korzystamy ze znanej nam instrukcji warunkowej, aby zdecydować z którym przypadkiem mamy do czynienia.
* – bardzo chciałbym abyście zapamiętali, że zmienna int jest 32-bitowa, a long long jest 64-bitowy. Taka wiedza w zupełności wam wystarczy do programowania konkursowego. Jednak zwykła, ludzka przyzwoitość karze mi tutaj zaznaczyć, że to nie jest prawda. C++ został stworzony w ten sposób, aby nadawał się do programowania mikro-kontrolerów i innych systemów, które wymagają ultra efektywnego języka programowania. Aby język C++ działał optymalnie również dla nich, zawiera różna kruczki z którymi możecie się nie spotkać nigdy w życiu. Na przykład to, że na 8-bitowych mikro-kontrolerach, zmienna typu int ma bitów szesnaście. Taka wiedza może się wam przydać jeśli będzie zajmować się systemami wbudowanymi (wydaje mi się, że wciąż w większości takich systemów zmienna int wciąż będzie 32-bitowa, ale ja się na tym nie znam) lub programowaniem na prehistorycznym sprzęcie. Może się zdarzyć również, że otrzymacie takie pytanie na rozmowie kwalifikacyjnej, bo jakiś bieda-rekruter chce was zmieszać z błotem (no chyba, że praca faktycznie wymaga takiej specjalistycznej wiedzy – wtedy takie pytanie ma sens).
