Notka pierwsza, w której poznajemy nasze pierwsze zadanie i je rozwiązujemy

Zamiast przydługawego wstępu, przejdźmy od razu do rzeczy. Oto nasze dzisiejsze zadanie:

---

Problem 1: Polski Chiński Mur

Tomek próbuje wybudować mur z klocków. Mur przypomina konstrukcję złożoną z dwóch rzędów trójkątów. Każdy z nich składa się z 2n-1 trójkątów. Rzędy są zwrócone do siebie dłuższą podstawą. Dla n = 7 konstrukcja wygląda następująco

Do konstrukcji Tomek używa klocka w kształcie rombu (klocek jest wielkości dwóch trójkątów). Teraz tomek zastanawia się na ile sposobów może on skonstruować swój mur.

Wejście

Na standardowym wejściu znajduje się jedna liczba naturalna n (1 ≤ n ≤ 1000) określająca wielkość konstrukcji.

Wyjście

Na standardowym wyjściu powinna się znaleźć jedna liczba naturalna – ilość sposobów na które Tomek może ułożyć swoją konstrukcję.

Przykład:

Dla danych wejściowych:

2

Poprawną odpowiedzią jest:

2

---

Zanim przejdziemy do rozwiązania zadania, zauważmy że składa się ono z czterech części:

1. Historyjki
2. Wejścia
3. Wyjścia
4. Przykładu

Historyjka to ta część w której dowiadujemy się jaka jest treść zadania. Często (tak jak w tym przypadku) to co naprawdę trzeba obliczyć jest ukryte pod płaszczykiem bajki. To co w historyjce jest ulicami, tak naprawdę dla nas może być grafem, talerze mogą być tak naprawdę stosem i tak dalej. Zadanie nigdy* nie powie Ci w jaki sposób masz coś policzyć. Wejście określa w jaki sposób podane nam są dane wejściowe. W tej sekcji należy szukać również jakie są ograniczenia dla różnych podanych nam wartości. Dla przykładu z sekcji “wejście” możemy się dowiedzieć, że wielkość n naszej zmiennej, nie będzie większa niż 1000. Możesz założyć, że dane wejściowe są poprawne i nie musisz ich sprawdzać w swoim programie. Wyjście określa w jaki sposób należy sformatować wyjście. W naszym przykładzie jest to łatwe, gdyż na wyjściu należy podać tylko jedną liczbę. Jednak gdy wartości jest więcej, musisz wiedzieć w jakiej kolejności należy je podać na wyjściu. Być może zauważyłeś, że w wejściu i wyjściu użyto dziwnego zwrotu “standardowe wejście” i “standardowe wyjście”. Opowiem o tym na jednej z przyszłych lekcji. W tej chwili możesz o tym myśleć w ten sposób, że wejście ma być wczytywane z klawiatury, a wynik zapisywany ma być na ekranie. Przykład prezentuje przykładowe wejście i poprawne wyjście dla zadanego wejścia. Możemy się w nim bliżej przyjrzeć w jaki sposób sformatowane jest wejście i wyjście oraz czy dobrze zrozumieliśmy treść zadania. Czasami w tej sekcji przykład jest wytłumaczony, czyli na przykład wytłumaczone mogłoby być dlaczego dla danych wejściowych n = 2 poprawnym wynikiem jest 2.

* – Wszystkie uogólnienia są fałszywe. Także to.

Rozwiązywanie zadań konkursowych można podzielić na dwie fazy. W pierwszej z nich sięgamy po kartkę i ołówek i próbujemy rozwiązać problem ręcznie. Gdy już wiemy jak go rozwiązać, siadamy do komputera i próbujemy napisać program, który rozwiązuje nasze zadanie.

Zacznijmy od pierwszej fazy. Spróbujmy policzyć na “kartce” na ile sposobów możemy skonstruować mur Tomka dla małych wartości n. Dla n = 1 istnieje dokładnie jeden taki sposób:

Dla wartości n = 2 mamy dwa takie sposoby:

Dla n = 3 mamy trzy takie sposoby:

Rozrysowując dalej, możemy zobaczyć, że dla n = 4 mamy cztery sposoby, a dla n = 5 mamy tych sposobów pięć. Możemy zauważyć tutaj pewną zależność. Wygląda na to, że liczba sposobów w jakie możemy ułożyć mur o wielkości n, wynosi n. Czy aby jednak na pewno? Matematyka zna przykłady w których możemy wysnuć błędne wnioski na podstawie rozwiązań dla małych wartości n. Mogę o nich kiedyś opowiedzieć. W takiej sytuacji mamy dwie możliwości. Możemy zaufać naszej intuicji i założyć, że rozwiązanie które wymyśliliśmy, jest poprawne, albo spróbować nasze rozwiązanie udowodnić. Dziś skorzystamy z tej drugiej możliwości.

Zauważmy, że aby skonstruować taki mur, dokładnie jeden romb musi zostać ustawiony pionowo. Jeśli żaden nie zostałby ustawiony pionowo, to romby z górnej i dolnej warstwy tworzyłyby długi równoległobok, a muszą tworzyć trapez, aby konstrukcja była pełna. Jeśli z kolei będą dwa pionowe romby (lub więcej) to nie damy rady wypełnić przestrzeni między nimi. Ponieważ dokładnie jeden romb musi zostać ustawiony pionowo, a jest dokładnie n miejsc w których możemy to zrobić, to oznacza, że istnieje dokładnie n sposobów na który można podaną konstrukcję stworzyć.

Taki krótki dowód musi nam w tej chwili wystarczyć. Przejdźmy teraz do drugiej części w której nasze rozwiązanie zapiszemy w postaci kodu programu.

Na konkursach można używać różnych języków programowania. Zdecydowana większość zawodników używa jednak języka C++. Podyskutujemy o tym więcej w następnej notce. Teraz przyjrzyjmy się jak wygląda szablon programu napisanego w C++:

#include <iostream>

using namespace std;

int main()
{
    // Tutaj dodaj swój kod

    return 0;
}

Pojawiło się tutaj sporo skomplikowanych koncepcji. Mamy funkcję, przestrzeń nazw oraz dyrektywę preprocesora. W dalszych lekcjach poznamy co wszystkie z tych linijek oznaczają. Na razie wystarczy zapamiętać, że szablon wygląda w ten sposób. Możesz również ten szablon zapisać sobie na dysku twardym. Nie zapomnij nadać plikowi rozszerzenie .cpp, które oznacza plik źródłowy języka C++.

Każdy program konkursowy można podzielić na trzy kroki:

• Wczytanie danych
• Obliczenie wyniku
• Wypisanie wyniku

W naszym zadaniu, obliczenie wyniku jest trywialne. Nie musimy nic robić! Za to aby wczytać dane, potrzebujemy zmiennej. Zmienna to takie miejsce w pamięci naszego programu do którego możemy zapisywać różne informacje. W języku C++ są różne rodzaje zmiennych. Nas interesuje taka zmienna, która mogłaby przechować liczbę naturalną z zakresu od 1 do 1000. Taką zmienną jest zmienna typu int (od ang. integer – liczba całkowita). Ponadto w języku C++ każdą zmienną, którą chcemy użyć w programie, musimy najpierw zadeklarować. Robi się to podając najpierw typ zmiennej (u nas int) a następnie podając nazwę tej zmiennej (u nas n – dobrą praktyką jest nazywanie zmiennych w ten sam sposób w jaki były one nazywane w treści zadania). Linijkę w języku C++ tradycyjnie kończymy symbolem średnika.

Mając już zmienną n, możemy wczytać dane. Służy do tego strumień cin (od ang character input – wejście znaków). Aby jej użyć do wczytania zmiennej n, najpierw piszemy cin, następnie wstawiamy dwa symbole większości >> a następnie wpisujemy nazwę zmiennej – u nas n. Linijkę w języku C++ tradycyjnie kończymy symbolem średnika.

Ostatnim krokiem będzie teraz wypisanie danych na standardowe wyjście. Do tego służy strumień cout (od ang character output – wyjście znaków). Aby wypisać zmienną za pomocą tego strumienia, należy najpierw wpisać jego nazwę: cout, następnie użyć dwóch symboli mniejszości << a następnie wpisać nazwę zmiennej, którą chcemy wypisać – u nas n. Aby dodatkowo po wypisaniu zmiennej n przejść do nowej linijki, należy ponownie użyć podwójnego symbolu mniejszości << a na końcu wpisać endl (od ang. end line – koniec linijki). Linijkę w języku C++ tradycyjnie kończymy symbolem średnika.

Początkujący programiści mogą mieć kłopot z zapamiętaniem kiedy należy stosować << a kiedy >>. Można to łatwo zapamiętać patrząc w którą stronę wskazuje strzałka. Przy wczytywaniu z wejścia wczytujemy wartość do zmiennej. Dlatego strzałka jest od wejścia do zmiennej. Przy wypisywaniu, wartość z zmiennej wypisujemy na wyjście. Dlatego strzałka jest od zmiennej do wyjścia.

Nasz program powinien wyglądać następująco:

#include <iostream>

using namespace std;

int main()
{
    int n;

    cin >> n;
    cout << n << endl;

    return 0;
}

W szczególności zwróć uwagę na wstawione spacje przed wszystkimi omawianymi instrukcjami. To tak zwane wcięcia. Na zawodach będziesz miał mało czasu aby napisać dobrze działający kod. Jeśli twój kod jest przejrzysty i czytelny, łatwiej i szybciej (o ułamki cennych sekund) jesteś w stanie się w nim połapać, zauważyć błędy i wnieść poprawki. Dlatego tak ważne jest, abyś od pierwszych programów nauczył się robić wcięcia. Zwłaszcza, że program działałby świetnie bez nich, a więc pokusa aby ich nie robić (zwłaszcza u początkujących programistów) jest ogromna.

Plik nauczymy się kompilować i uruchamiać na następnych zajęciach. W tej chwili jeśli chcesz uruchomić i zobaczyć jak działa nasz program, możesz użyć internetowego ideone.

Brawo! W ten sposób udało Ci się rozwiązać pierwsze zadanie konkursowe! Przed Tobą jeszcze długa droga zanim zostaniesz mistrzem świata w programowaniu. Ale pierwszy krok został zrobiony! I pamiętaj: linijkę w języku C++ tradycyjnie kończymy symbolem średnika.