Zadania trzeciego etapu Konkursu Informatycznego dla gimnazjalistów LOGIA 06

Zadanie 1 (pary liczb trójkątnych).

Na II etapie konkursu jedno z zadań dotyczyło liczb trójkątnych. Dla przypomnienia, rysunki obok przedstawiają graficzną ilustrację kolejnych liczb trójkątnych.

Napisz funkcję NATR :ll, której daną jest lista dodatnich liczb całkowitych nie większych niż 200. Wynikiem funkcji jest lista par liczb przedstawiających liczby danej :ll jako sumy dwóch liczb trójkątnych. Nie każda liczba da się przedstawić jako suma dwóch liczb trójkątnych, wówczas takiej liczbie odpowiada lista pusta. Dla niektórych liczb istnieje więcej niż jedna taka para, wówczas na liście wynikowej może wystąpić dowolna z tych par. Kolejność liczb w obrębie pary jest także dowolna.

Wynikiem NATR [94 2 3 4 5 30 81] jest [[3 91][1 1][][1 3][][15 15][78 3]].
  Prawidłowym wynikiem jest też
[[66 28][1 1][][3 1][][15 15][66 15]]
  lub [[66 28][1 1][] [3 1][][15 15][45 36]]

Zadanie 2 (haft krzyżykowy).

Haft krzyżykowy - rodzaj haftu, w którym na materiale w formie siatki o jednakowej na całej powierzchni gęstości oczek (kanwie) wykonuje się tzw. "krzyżyki". Są to podstawowe elementy haftu krzyżykowego. Powstają one przez przeplecenie kolorowej nici przez oczko kanwy, a następnie wykonanie tego samego w taki sposób, aby kolejna część nitki pokryła poprzednią, przecinając ją pod kątem prostym (krzyżyk).

Napisz procedurę HAFT :ll, której daną jest niepusta lista nieujemnych liczb całkowitych. Procedura tworzy rysunek kwadratowego elementu wyszywanego w dwóch kolorach - czerwonym i czarnym; miejsca niewyszywane przedstawiamy za pomocą jasnoszarych krzyżyków. Przyjrzyj się poniższym przykładom i wywnioskuj, jaka reguła rządzi powstawaniem rysunków.

Są to wyniki wywołania HAFT [0 1 2 3 4 5 6 7 8], HAFT [26 16 3] oraz
HAFT [1512 18168 50288 49532 49208 18600 16728 49640 50324 13128]

Każda liczba na liście jest zaszyfrowanym opisem jednego wiersza krzyżyków. Wielkość kwadratowego motywu jest określona przez długość listy :ll. Rysunek musi mieścić się w całości na ekranie i wykorzystywać co najmniej 3/4 wysokości ekranu. Maksymalna długość listy wynosi 50, wartości liczb zależą od długości listy i zawsze są prawidłowe.

Zadanie 3 (pokrycie).

Na kwadratowym trawniku o rozmiarach 20×20 położono prostokątne maty. Ułożenie każdej maty i jej rozmiar opisujemy za pomocą czterech liczb całkowitych z zakresu od 0 do 20: [x1 y1 x2  y2], gdzie [x1 y1], [x2 y2] to współrzędne dwóch przeciwległych wierzchołków prostokąta. Zakładamy, że x1≤x2 oraz y1≤y2. Mata [0 0 20 20] pokrywa cały trawnik, mata [10 10 20 20] - jego "górną prawą" ćwiartkę. Układ mat można zapisać w postaci listy opisów mat, np. [[10 10 20 20] [0 0 20 10] [8 8 12 12]].

Zdefiniuj funkcję NIEPOKRYTE :um, której wynikiem - dla danego układu mat :um - jest liczba określająca pole powierzchni nieprzykrytej części trawnika.

Wynikiem NIEPOKRYTE [[10 10 20 20] [0 0 20 10] [8 8 12 12]] jest 96.

Zadanie 4 (szyfr Cezara).

Szyfr Cezara polega na zastąpieniu każdego kolejnego znaku szyfrowanego tekstu znakiem występującym w alfabecie o określoną liczbę pozycji dalej, cyklicznie (tj. jeśli wykraczamy poza alfabet, to kolejne znaki bierzemy z początku alfabetu). Nasz alfabet będzie składał się z małych liter alfabetu łacińskiego oraz spacji. Przyjmujemy, że spacja jest następnym znakiem po literze z.

Napisz funkcję SZYFR :ls :klucz, której danymi są :ls - lista słów składających się z małych liter alfabetu łacińskiego oraz liczba naturalna :klucz. Wynikiem funkcji jest lista słów składających się z małych liter alfabetu łacińskiego powstała po zaszyfrowaniu danej :ls szyfrem Cezara o kluczu :klucz. Kodowaniu podlegają także odstępy pomiędzy słowami. Dwa sąsiednie znaki szyfrowanego tekstu nie mogą być identyczne. Gdyby skrajne (pierwszy bądź ostatni) znaki kodowanego tekstu miały być zaszyfrowane jako spacja, to są pomijane w wyniku.

Wynikiem SZYFR [hokus pokus abrakadabra] 26 jest [gnjtrzonjtrz aq j c aq].
Wynikiem SZYFR [zuzia je szczaw] 1 jest [v jbakfat d bx].