Strona główna » Poradniki » Logomocja » LOGIA » Logia 2018/19 Etap II
 

Logia 2018/19 Etap II

https://mattomatti.com/li182
Oryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1

Wojtek koduje rysunki złożone z kwadratów za pomocą napisów. Kolejne znaki kodu oznaczają numery wierszy i nazwy kolumn, w których kwadraty są zamalowane. Numery wierszy i nazwy kolumn są podane w porządku rosnącym. Na przykład kod 1BCD2AC3BD4ABC5B oznacza, że w pierwszym wierszu są zamalowane kwadraty w kolumnach B, C i D, wdrugim w kolumnach A i C itd. Zdefiniuj jednoparametrową procedurę/funkcję kod, po wywołaniu której powstanie siatka zamalowanych kwadratów zakodowanych przez Wojtka. Parametrem jest słowo określające kod. Minimalna liczba wierszy wynosi 8, maksymalna 26, a kolumny są oznaczane wielkimi literami alfabetu łacińskiego od A do M. Po każdej liczbie występuje co najmniej jedna litera. Liczba wierszy i kolumn jest wyznaczona przezostatni zamalowany kwadrat odpowiednio nadole orazz prawej strony rysunku. Wysokość rysunku jest stała i wynosi 468. Rysunek powinien być na środku ekranu.

Rysunek pomocniczy
kod "1CD2BDE3AD4BCD6BCE7CD8AC
kod "1BCDEFG2AH3BDEG4CF5DE6DEG7BCDEFG8BDE9DE10CF11CF12BCEF

Rozwiązanie

Zadanie należy podzielić na dwa etapy. W pierwszym etapie należy przeanalizować wczytane dane i ewentualnie przetworzyć je na prostsze, aby łatwiej na ich podstawie narysować rysunek. W drugim etapie zostanie narysowany rysunek.

Na początku deklarowana jest lista cyfr oraz liter. Następnie przyjmujemy, że obrazek początkowo ma długość i szerokość zerową. Na końcu danych wstawiamy wartownika w postaci znaku #. Dopóki nie dojdziemy do wartownika to w pętli odczytujemy liczbę, a następnie wszystkie następujące litery. Każdy odczytany znak jest od razu usuwany z danych. Dodatkowo w pętli aktualizowany jest aktualny rozmiar siatki.

  1. oto kod :kod
  2.   niech "cyfry "0123456789
  3.   niech "litery "ABCDEFGHIJKLM
  4.   niech "wierszy 0
  5.   niech "kolumn 0
  6.  
  7.   niech "kod (słowo :kod "#)
  8.   niech "pozycje []
  9.  
  10.   dopóki [:kod <> "#] [
  11.     niech "wiersz 0
  12.     dopóki [numel (pierw :kod) :cyfry <> 0][
  13.       niech "wiersz :wiersz*10 + (numel (pierw :kod) :cyfry) - 1
  14.       niech "kod bp :kod
  15.     ]
  16.     dopóki [numel (pierw :kod) :litery <> 0][
  17.       niech "x numel (pierw :kod) :litery
  18.       niech "pozycje nak (lista :wiersz :x) :pozycje
  19.       jeśli (:x > :kolumn) [
  20.         niech "kolumn :x
  21.       ]
  22.       niech "kod bp :kod
  23.     ]
  24.     jeśli (:wiersz > :wierszy) [
  25.       niech "wierszy :wiersz
  26.     ]
  27.   ]

Drugi etap rozpoczynamy od obliczenia boku kwadratów z których składa się z siatka. Następnie rysowana jest siatka. Podczas rysowania konkretnego kwadratu algorytm sprawdza czy jego pozycja znajduje się na liście. Jeśli tak to zostaje on dodatkowo zamalowany.

  1.   niech "a 468 / :wierszy
  2.   pod
  3.   np :a * :wierszy / 2 pw 90
  4.   np :a * :kolumn / 2 pw 90
  5.   opu
  6.   powtórz (:wierszy) [
  7.     niech "x npw
  8.     powtórz (:kolumn) [
  9.       niech "y :kolumn - npw + 1
  10.       powtórz 4 [
  11.         np :a pw 90
  12.       ]
  13.       jeśli (numel (lista :x :y) :pozycje <> 0) [
  14.         wielokąt [
  15.           ukm "czarny
  16.           powtórz 4 [
  17.             np :a pw 90
  18.           ]
  19.         ]
  20.       ]
  21.       pw 90 np :a lw 90
  22.     ]
  23.     pw 90 ws :a*:kolumn
  24.     lw 90 np :a
  25.   ]
  26. już

Zadanie 2

Bitowo Dolne ma jedną linię tramwajową z m przystankami. Przystanki oznaczone są kolejnymi wielkimi literami alfabetu łacińskiego. Tramwaj wyrusza z przystanku oznaczonego literą Aizatrzymuje się na co n-tym przystanku, naktórym jeszcze nie stawał. Tramwaj porusza się ruchem wahadłowym, czyli po dotarciu do krańcowego przystanku zawraca. Twoim zadaniem jest ustalenie rozkładu jazdy tramwaju.

Napisz dwuparametrową funkcję o nazwie tram, której parametrami są dwie liczby naturalne, odpowiednio m i n. Wynikiem jest słowo określające kolejne przystanki, na których tramwaj zatrzymuje się. Pierwszy parametr może przyjmować wartości od 1 do 26, a drugi od 1 do 1000.

tram 6 5EADCBF
tram 4 7ADCB

Rozwiązanie

Pierwszy etap polega na przygotowaniu listy przystanków. Do kontrolowania kierunku jazdy tramwaju używana jest zmienna kierunek, a aktualny przystanek wskazuje teraz. Następnie pętla jest wykonywana dopóki wszystkie przystanki nie znajdą się w rozkładzie. Pętla polega na przesuwaniu się po przystankach, aż minie m nieodwiedzonych przystanków. Po dotarciu na przystanek należy dołączyć do rozkładu aktualnie odwiedzony przystanek.

  1. oto tram :m :n
  2.   niech "przystanki "
  3.   powtórz (:m) [
  4.     niech "przystanki nak znak(npw + 64) :przystanki
  5.   ]
  6.   niech "rozkład "
  7.   niech "kierunek 1
  8.   niech "teraz 0
  9.   dopóki [długość :rozkład <> długość :przystanki][
  10.     niech "licznik 1
  11.     dopóki [:licznik <= :n][
  12.       jeżeli (:teraz = 1) [
  13.         niech "kierunek 1
  14.         zwiększ "teraz
  15.       ][
  16.         jeżeli (:teraz = :m) [
  17.           niech "kierunek -1
  18.           zmniejsz "teraz
  19.         ][
  20.           niech "teraz :teraz + :kierunek
  21.         ]
  22.       ]
  23.       jeśli (numel (element :teraz :przystanki) :rozkład = 0)[
  24.         zwiększ "licznik
  25.       ]
  26.     ]
  27.     niech "rozkład nak (element :teraz :przystanki) :rozkład
  28.   ]
  29.   wynik :rozkład
  30. już

Zadanie 3

Ania konstruuje pajęczaki i opisuje swoje projekty przy pomocy słów złożonych z wielkich liter Z, J, D, T. Pajęczaki są zbudowane z rozgałęziających się węzłów, jedna litera określa jeden węzeł. Litera Z (zero) oznacza, że dany węzeł nie ma rozgałęzień, J (jeden), D (dwa), T (trzy), że z węzła wychodzą odpowiednio jedna/dwie/trzy gałęzie. Środek pajęczaka to pierwsza litera jego opisu, następne opisują jego rozgałęzienia w głąb.

DJZZ
TDZZJZJJZ
TZJDZZZ

Napisz jednoparametrową funkcję stp, której parametrem jest niepuste słowo o długości conajwyżej 100 opisujące pajęczaka. Wynikiem jest stopień pajęczaka, czyli liczba węzłów od środka do najdalszego węzła.

stp "JDJDZJDZZZ jest 7
stp "TJJJDZZDZZJZ jest 6

Rozwiązanie

Najprostszym rozwiązaniem tego zadania jest zastosowanie rekurencji. Funkcja będzie wywoływać samą siebie i zwracać dwa argumenty: znalezioną długość i aktualny stan ścieżki. Podczas każdego wykonania funkcji usuwamy pierwszy znak z danych i go analizujemy. Jeśli natrafimy na Z to zwracamy długość 1. Jeśli na jakikolwiek inny znak to funkcja wywoła samą siebie odpowiednie J (jeden), D (dwa) lub T (trzy) razy. Podczas każdego wywołania należy pamiętać o aktualizacji danych i wybraniu najdłuższej ścieżki pośród wszystkich X rozgałęzień.

  1. oto stp_rek :słowo
  2.   niech "znak pierw :słowo
  3.   niech "słowo bp :słowo
  4.   jeśli (:znak = "Z) [
  5.     wynik (lista 1 :słowo)
  6.   ]
  7.   niech "ile "JDT
  8.   niech "maks 0
  9.   powtórz (numel :znak :ile) [
  10.     niech "w stp_rek :słowo
  11.     niech "dl (pierw :w) + 1
  12.     jeśli (:dl > :maks) [
  13.       niech "maks :dl
  14.     ]
  15.     niech "słowo ost :w
  16.   ]
  17.   wynik (lista :maks :słowo)
  18. już

Funkcja stp ma za zadanie zwrócić tylko długość, więc dodatkowo piszemy funkcję, która wywoła rekurencyjną wersję i zwróci odpowiedni element.

  1. oto stp :słowo
  2.   wynik pierw stp_rek :słowo
  3. już