Strona główna » Poradniki » Logomocja » LOGIA » Logia 2014/15 Etap III
 

Logia 2014/15 Etap III

· Etap I · Etap II · Etap III ·
Oryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1 (szyfr)

Kuba koduje teksty za pomocą szyfrów obrazkowych. Najpierw ustala alfabet zawierający litery, które będą występować w szyfrowanym słowie. Następnie koduje słowo za pomocą prostokątów o różnych wymiarach. Wysokość prostokąta odpowiadającego kolejnej literze słowa zależy od jej pozycji w alfabecie i wynosi, odpowiednio, 10 dla pierwszej litery alfabetu, 20 dla drugiej, 30 dla trzeciej itd. Szerokość prostokąta zależy od pozycji litery w szyfrowanym słowie i jest równa 10 dla pierwszej litery słowa, 20 dla drugiej, 30 dla trzeciej itd.

Julka odszyfrowuje zakodowany tekst – zdanie, w którym spacje zakodowane zostały za pomocą prostokątów o wysokości 0 (odcinków).

Napisz dwuparametrową funkcję deszyfr, której wynikiem jest lista odkodowanych słów. Pierwszy parametr jest alfabetem i składa się z co najwyżej 26 liter (małe litery alfabetu łacińskiego). Drugi parametr to lista dwuelementowych list określających wysokości i szerokości prostokątów stanowiących elementy zaszyfrowanego zdania.

deszyfr "acdeh [[10 20][30 10][50 40][20 30]]jest [dach]
deszyfr "rklotam [[60 10][30 20][60 30][0 40][70 50][60 60][0 70][20 80][40 90][50 100][60 110]]jest [ala ma kota]

Odszyfrowanie

W celu odszyfrowania zaszyfrowanych znaków należy wpierw uporządkować dane. Pierwsza liczba szyfrująca znak to wysokość i oznacza pozycję w słowie pomnożoną przez 10. Po posortowaniu wystarczy odszyfrować znak kodowany przez drugą liczbę z pary. W tym celu należy wartość podzielić przez 10, a następnie pobrać odpowiedni znak z alfabetu. Nie należy zapominać, że wysokość 0 oznacza znak przerwy tj. spację. Jednym z rozwiązań jest umieszczenie na początku alfabetu brakujący znak.

Rozwiązanie

Poniżej znajduje się gotowe rozwiązanie zadania implementujące podaną wyżej strategie.

  1. oto deszyfr :alfabet :lista
  2.   niech "alfabet (słowo znak 32 :alfabet)
  3.   niech "l []
  4.   powtórz (długość :lista) [
  5.     niech "el element npw :lista
  6.     niech "z element (((pierw :el) / 10)+1) :alfabet
  7.     niech "l nak (lista ost :el :z) :l
  8.   ]
  9.   niech "l sortuj :l
  10.   niech "s "
  11.   powtórz (długość :l) [
  12.     niech "s nak (ost (element npw :l)) :s
  13.   ]
  14.   wynik :s
  15. już

(2.) Na początku dopisujemy na początku alfabetu znak spacji i (3.) deklarujemy nową listę. Następnie listę (4. - 8.) uzupełniamy parami szerokość szyfrowanego znaku oraz jego znak pobrany z alfabetu. Dalej (9.) sortujemy dane (tutaj są sortowane względem pierwszej wartości z każdej pary). Dalej pozostaje (10. - 13.) pobrać znaki z każdej pary po kolei i (14.) zwrócić wynik.

Zadanie 2 (redukcja)

Janek bawi się cyframi i zapisuje je na kwadratowej tabliczce o wymiarach n x n (2 ≤ n ≤ 20). Następnie przechyla tabliczkę i liczby spadają w jednym z czterech kierunków. Dodatkowo następuje redukcja – jeśli dwie sąsiednie (licząc zgodnie z kierunkiem spadania) liczby są takie same, to zastępowane są ostatnią cyfrą ich sumy. Zastępowanie kontynuowane jest dla pozostałych liczb w wierszu (kierunki lewo-prawo) lub kolumnie (kierunki góra-dół). Analiza danego wiersza/kolumny powtarzana jest aż do momentu, gdy nie uda się dokonać żadnej takiej zamiany.

Napisz dwuparametrową funkcję redukcja, której pierwszym parametrem jest lista list opisujących kolejne wiersze tabliczki (0 – oznacza puste miejsce), a drugim – słowo opisujące sekwencję kolejnych pochyleń (l oznacza kierunek w lewo, p – prawo, g – górę, d – dół) . Wynikiem jest stan tabliczki po przekształceniach. Maksymalna długość słowa będącego drugim parametrem to 1000.

redukcja [[0 2 4][4 4 8][4 0 8]] "dldldjest [[0 0 0][0 0 0][4 0 0]]
redukcja [[1 1 1 1][1 1 1 1][1 1 1 1][1 1 1 1]] "lpdgjest [[0 0 0 6][0 0 0 0][0 0 0 0][0 0 0 0]]
Rozwiązanie

Zadanie 3 (wykreślanka)

Sławek bawi się słowem i usuwa z niego litery. Chce, by pewne trzy wyróżnione litery występowały w zadanej kolejności, choć niekoniecznie obok siebie. Zapisuje wszystkie powstałe w ten sposób słowa w uporządkowanej alfabetycznie liście.

Napisz funkcję abc, o trzech parametrach, której pierwszym parametrem jest słowo, którym bawi się Sławek, nie dłuższe niż dziesięcioliterowe, zawierające jedynie małe litery alfabetu łacińskiego. Drugim parametrem jest trzyliterowe słowo, składające się z liter wyróżnionych przez Sławka. Wynikiem funkcji jest to słowo z listy Sławka, które znajduje się w niej na pozycji określonej trzecim parametrem funkcji. Trzeci parametr może przyjmować wartości od 1 do 5000. Jeśli jego wartość jest większa niż liczba elementów listy Sławka, to wartością funkcji jest słowo puste.

abc "abebc "abc 5 jest "aebc (bo jest piątym elementem listy Sławka: [abbc abc abebc abec aebc])
abc "xabacxy "abc 3 jest "abacxy (w tym przypadku początkowe elementy listy Sławka to "abac, "abacx, "abacxy)
Rozwiązanie

Zadanie 4 (jaszczurka)

Wzdłuż ulicy stoją domy. Jedne z nich stykają się bocznymi ścianami, a pomiędzy innymi może być wolne miejsce. Jaszczurka wędruje po dachach. Rozpoczyna swoją podróż na poziomie ziemi przed pierwszym domem, wspinając się pionowo na jego dach. Następnie porusza się po kolejnych dachach, pomiędzy domami wchodząc wyżej (gdy kolejny dom jest wyższy od poprzedniego) lub schodząc (gdy kolejny dom jest niższy), być może nawet do poziomu ziemi (gdy napotka wolne miejsce pomiędzy kolejnymi domami). Swoją podróż kończy na poziomie ziemi za ostatnim domem.

Napisz jednoparametrową funkcję droga, której parametrem jest lista, składająca się z dwuelementowych list opisujących szerokości i wysokości kolejnych domów oraz ewentualnie pojedynczych liczb opisujących odległości pomiędzy domami. Wynikiem funkcji jest długość drogi przebytej przez jaszczurkę.

droga [[40 20][50 30]10[20 20]20[40 10]]jest 300

Rozwiązanie

W celu rozwiązania zadania należy zauważyć, że potrzebne są dwa liczniki, które w rozwiązaniu nazwane zostały p i suma. Oznaczają one kolejno wysokość na jakiej znajduje się jaszczurka oraz jaka drogę już przeszła.

  1. oto droga :domy
  2.   niech "p 0
  3.   niech "suma 0
  4.   powtórz (długość :domy) [
  5.     niech "el element npw :domy
  6.     jeżeli (lista? :el) [
  7.       niech "suma :suma + abs(:p - ost :el)
  8.       niech "p ost :el
  9.       niech "suma :suma + (pierw :el)
  10.     ][
  11.       niech "suma :suma + :p + :el
  12.       niech "p 0
  13.     ]
  14.   ]
  15.   wynik :suma + :p
  16. już

(4.) Dla każdego elementu: (5.) pobierz element i (6.) sprawdź czy opisuje dom. Jeśli tak to (7. - 9.) prześledź podróż jaszczurki uwzględnijąc, że musi się wspiąć. W przeciwnym razie (11. - 12.) sprowadź jaszczurkę na ziemie, przesuń o wskazaną przerwę między domami i ustal jej poziom na 0. Na koniec (15.) należy pamiętać, że jaszczurka kończy podróż na ziemi!