Strona główna » Poradniki » Logomocja » LOGIA » Logia 2010/11 - Etap II
 

Logia 2010/11 - Etap II

https://mattomatti.com/li102
· Etap I · Etap II · Etap III ·
Oryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Zadanie 1

W klasie Oli zapanowała moda na kolorowe szlaczki rysowane w zeszytach. Każdy chciał mieć oryginalny szlaczek wymyślony tylko dla siebie. Ola postanowiła przygotować specjalny program do projektowania szlaczków złożonych z kwadratów w dwóch kolorach. Umówiła się z koleżankami, że otrzyma od nich dwie informacje - wysokość szlaczka oraz opis tworzących go kwadratów. Rysunki wydały jej się smutne, więc postanowiła dodać trzeci kolor - czerwony, w ten sposób, że w tych kolumnach rysowanego szlaczka, w których jest najwięcej szarych kwadratów, zastąpiła je kwadratami czerwonymi.

Pomóż Oli projektować szlaczek i napisz procedurę WZOREK :h :s rysującą na środku ekranu szlaczek o szerokości 600 lub wysokości 400, złożony z szarych, czerwonych i białych kwadratów. Parametr :h określa wysokość szlaczka i może przyjmować wartości od 2 do 20. Parametr :s jest słowem opisującym wygląd szlaczka zgodnie z następującymi zasadami:

  • opisuje kolory kolejnych kwadratów, kolumnami, poczynając od lewego dolnego kwadratu,
  • składa się z jedynek i zer, jedynka oznacza kwadrat szary, zaś zero - biały,
  • jego długość jest wielokrotnością :h.
WZOREK 2 "10111001011011
WZOREK 3 "101010111010101010111
WZOREK 5 "10001011101000101010

Strategia

Ze względu na fakt, że dane są przekazane kolumna po kolumnie od dołu do góry to rysowanie najlepiej rozpocząć od lewego dolnego rogu. Należy tutaj pamiętać, że rysunek może być pionowo lub poziomo zorientowany, więc należy odpowiednio dobrać rozmiar pól.

Rysowanie całego wzorku warto podzielić na dwa etapy. Pierwszy z nich będzie polegał na narysowaniu szaro-białego wzorku na podstawie kodu. Dopiero potem w drugim etapie wystarczy sprawdzić, które kolumny zamalowane na czerwono i w jakiej części. W celu optymalizacji działania programu w trakcie pierwszego etapu warto na bieżąco zliczać ilość szarych pól w każdej kolumnie oraz szukać maksimum.

Rozwiązanie

  1. oto WZOREK :h :s
  2.   niech "dl długość :s
  3.   niech "w :dl / :h
  4.   niech "aszer 600 / :w
  5.   niech "awys 400 / :h
  6.   jeżeli (:aszer < :awys) [
  7.     niech "a :aszer
  8.   ][
  9.     niech "a :awys
  10.   ]
  11.   pod
  12.   ws :a*:h/2 pw 90
  13.   ws :a*:w/2 lw 90
  14.   opu

Początkowo pobieramy (2.) ilość pól i (3.) wyliczamy ile będzie kolumn. Na tej podstawie (4. - 5.) wyliczamy ile by miały kafelki dopasowane na szerokość i wysokość i (6. - 10.) wybieramy mniejszą wartość. Zagwarantuje to, że rysunek zawsze się zmieści w wyznaczonym obszarze 600×400. Po wyliczeniach (11. - 14.) przechodzimy do rysowania szaro-białych pól.

  1.   niech "szarych []
  2.   niech "maks 0
  3.   powtórz (:w) [
  4.     niech "ile 0
  5.     niech "przes (npw - 1) * :h
  6.     powtórz (:h) [
  7.       niech "el element (npw + :przes) :s
  8.       jeżeli (:el = "0)[
  9.         ukm "biały
  10.       ][
  11.         ukm "szary
  12.         zwiększ "ile
  13.       ]
  14.       wielokąt [
  15.         powtórz 4 [
  16.           np :a
  17.           pw 90
  18.         ]
  19.       ]
  20.       pod
  21.       np :a
  22.       opu
  23.     ]
  24.     pod
  25.     ws :a*:h lw 90
  26.     ws :a pw 90
  27.     opu
  28.     niech "szarych nak :ile :szarych
  29.     jeśli (:ile > :maks) [
  30.       niech "maks :ile
  31.     ]
  32.   ]

Przed rysowaniem deklarujemy (15.) listę :szarych na którą będą wrzucane ilości szarych pól w kolejnych kolumnach oraz (16.) :maks, która będzie przechowywać największą ilość szarych pól wśród kolumn. (17. - 46.) Rozpoczynamy proces rysowania; (18.) inicjalizujemy licznik :ile, aby zliczyć szare pola i (19.) wyliczamy przesunięcie względem którego będą odczytywane kolejne wartości. Na koniec (42.) dopisujemy kolejną ilość szarych pól na listę i (43. - 54.) sprawdzamy czy nie padła ich nowa, maksymalna ilość.

  1.   pod
  2.   lw 90 np :a*:w
  3.   pw 90
  4.   opu
  5.   powtórz (:w) [
  6.     niech "przes (npw - 1) * :h
  7.     jeśli (element npw :szarych = :maks) [
  8.       powtórz (:h) [
  9.         niech "el element (npw + :przes) :s
  10.         jeżeli (:el = "0)[
  11.           ukm "biały
  12.         ][
  13.           ukm "czerwony
  14.         ]
  15.         wielokąt [
  16.           powtórz 4 [
  17.             np :a
  18.             pw 90
  19.           ]
  20.         ]
  21.         pod
  22.         np :a
  23.         opu
  24.       ]
  25.       ws :a*:h
  26.     ]
  27.     pod
  28.     pw 90
  29.     np :a lw 90
  30.     opu
  31.   ]
  32. już

(47. - 50.) Wracamy do lewego dolnego rogu, aby jeszcze raz narysować, ale tylko nakładając czerwone pola. W tym celu (51. - 77.) ponownie wykonujemy te same polecenia, ale tylko dla kolumn z taką ilością szarych pól jaką wartość ma maksymalna ich ilość. Podczas rysowania kolumny wystarczy szary kolor zamienić na czerwony, a biały pozostawić bez zmian.

Zadanie 2

Słowo palindrom pochodzi od greckiego słowa palindromeo - biec z powrotem. Palindrom to takie wyrażenie, które jest identyczne, jeśli czytamy je od lewej do prawej i od prawej do lewej, przykładowo: oko, inni, kajak, inniwinni, kobyłamamałybok.

Napisz funkcję ILEP :s, której wartością jest liczba palindromów zawartych w słowie :s, składającym się jedynie z małych liter.

ILEP "kajak jest 7, bo kajak zawiera palindromy k, a, j, a, k, aja, kajak
ILEP "mama jest 6, bo mama zawiera palindromy m, a, m, a, mam, ama

Strategia

Szukając palindromów zawartych w słowie :s to wiemy, że musi to być ciąg znaków wyjęty z :s, ale nie może być to np. pierwsza i ostatnia litera, ponieważ nie jest to fragment :s. Strategia polega na znalezieniu wszystkich fragmentów od wartości 1 do długości :s używając do tego podwójnej pętli.

Rozwiązanie

Oto przykładowe rozwiązanie:

  1. oto ILEP :s
  2.   niech "licznik 0
  3.   powtórz (długość :s) [
  4.     niech "ile npw
  5.     powtórz ((długość :s) - :ile + 1) [
  6.       niech "p npw - 1
  7.       niech "t "
  8.       powtórz (:ile) [
  9.         niech "t (słowo :t element :p + npw :s)
  10.       ]
  11.       jeśli (:t = wspak :t) [
  12.         zwiększ "licznik
  13.       ]
  14.     ]
  15.   ]
  16.   wynik :licznik
  17. już

Na początku (2.) inicjalizujemy :licznik palindromów i (3.) rozpoczynamy poszukiwania fragmentów. (4.) Pierwsza pętla będzie określać długość szukanego fragmentu. Kolejno to będą 1, 2, .. aż do długości :s. (5.) Dla każdej takiej pętli istnieje odpowiednia ilość fragmentów unikalnych. Numer powtórzenia drugiej pętli określa od którego znaku należy wybrać :ile znaków. Dalsza część jest bardzo prosta: (7. - 10.) wybranie odpowieniego fragmentu oraz (11.) sprawdzenie czy wybrany fragment :t jest palindromem. Jeśli jest to (12.) zwiększamy :licznik, który (16.) na koniec zwracamy.

Zadanie 3

Pionek porusza się po prostokątnej planszy, w każdym ruchu przesuwając się o jedno pole w jednym z czterech kierunków: w lewo, w prawo, w górę, w dół. Poszczególne pola planszy zawierają cyfry.

Napisz funkcję PIONEK :w :p :c, która dla planszy składającej się z :w wierszy, opisanej słowem :p, wyliczy minimalną liczbę ruchów, jaką musi wykonać pionek, aby przejść pomiędzy dwoma polami zawierającymi cyfrę :c. Słowo :p zawiera ciąg cyfr opisujących zawartość kolejnych pól planszy, wierszami, poczynając od lewego górnego pola. Zakładamy, że cyfra :c występuje na planszy co najmniej dwa razy, a także poprawną długość słowa :p.

PIONEK 1 "444474744474 7 jest 2, patrz rysunek poniżej
PIONEK 2 "444474744474 7 jest 1, patrz rysunek poniżej
PIONEK 3 "532378832375 5 jest 5, patrz rysunek poniżej

Strategia

Przypiszmy każdemu polu na planszy pewna pozycję tj. punkt w którym dana wartość się znajduje. Następnie należy spisać wszystkie pola na których znajduje się wartość :c. Z tak przygotowanej listy można wybrać wszystkie możliwe pary punktów pomiędzy którymi trzeba przejść. Wtedy należy wybrać wśród takich dróg tą o najmniejszej długości.

Wyliczanie przejścia z punktu (x1, y1) do (x2, y2) to dodanie potrzebnych kroków do przejści w pionie i poziomie. Niezależnie od wybranej ścieżki, ale z każdym krokiem zbliżając się do celu to odległość wynosi |x1 - x2| + |y1 - y2|.

Przykładowa funkcja do wyliczenia odległości pomiędzy punktami dla dwóch pewnych punktów :p1 i :p2 reprezentowanych przez dwuelemementową listę wygląda następująco:

  1. oto PIONEK_odl :p1 :p2
  2.   niech "a abs((pierw :p1) - (pierw :p2))
  3.   niech "b abs((ost :p1) - (ost :p2))
  4.   wynik :a + :b
  5. już

Rozwiązanie

Pierwszy etap polega na znalezieniu wszystkich wartości :c występujących w przekazanym kodzie :p. (8.) Dla każdej takiej wartości na listę :pozycje (9.) wrzucana jest dwuelementowa lista opisująca położenie danego pola.

  1. oto PIONEK :w :p :c
  2.   niech "pozycje []
  3.   niech "h (długość :p) / :w
  4.   powtórz (:w) [
  5.     niech "x npw
  6.     niech "przes (npw - 1) * :h
  7.     powtórz (:h) [
  8.       jeśli (element :przes+npw :p = :c) [
  9.         niech "pozycje nak (lista :x npw) :pozycje
  10.       ]
  11.     ]
  12.   ]

Z kolei w drugiej części porównywane są odległości pomiędzy każda możliwą parą punktów. (13.) Początkowo za odległość potrzebną do przebycia przypisujemy :h + :w czyli najdłuższa możliwa trasa z jednego kąta mapy do drugiego. Podczas wykonywaine kodu (18.) napotkamy ograniczenie, które optymalizuje działanie programu, bo nie sprawdzamy dwa razy odległości pomiędzy pewnymi punktami :p1 i :p2. Ponadto nie porównujemy dwóch taki samych punktów co by skutkowało zawsze odpowiedzią 0.

  1.   niech "odl :w + :h
  2.   powtórz (długość :pozycje) [
  3.     niech "x npw
  4.     powtórz (długość :pozycje) [
  5.       niech "y npw
  6.       jeśli (:y > :x) [
  7.         niech "odlt PIONEK_odl (element :x :pozycje) (element :y :pozycje)
  8.         jeśli (:odlt < :odl) [
  9.           niech "odl :odlt
  10.         ]
  11.       ]
  12.     ]
  13.   ]
  14.   wynik :odl
  15. już