Strona główna » Poradniki » Logomocja » LOGIA » Logia 2015/16 Etap III
 

Logia 2015/16 Etap III

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

Zadanie 1 (wycieczka)

Miasta w Logolandii są ponumerowane i połączone specyficzną siecią dróg. Każda droga łączy dwa różne miasta. Z każdego miasta można dotrzeć do dowolnie wybranego innego, pokonując jedną lub więcej dróg bez cofania się – tylko na jeden sposób. Jedno z miast jest wyróżnione i nazywane jest stolicą. Stolica połączona jest z resztą kraju co najwyżej dwiema drogami, a każde inne miasto – co najwyżej trzema.

Schemat miasta

Małgosia, Karol i Paweł podczas wspólnej wycieczki odwiedzają wszystkie miasta Logolandii, bez zbędnych przejść. Wyruszają ze stolicy i w niej kończą wycieczkę. Na przykład, załóżmy że Logolandia wygląda tak, jak na rysunku przykładowym, stolica ma numer 4 i trasa wycieczki przebiega kolejno przez miasta 4, 2, 1, 2, 3, 2, 4, 5, 6, 5 i 4. Każdy uczestnik wycieczki zapisuje trasę według własnych zasad, ale każde miasto jest zapisywane tylko raz.

Małgosia zapisuje miasto już podczas pierwszego pobytu w nim. W przykładzie kolejne miasta zapisane przez Małgosię to 4, 2, 1, 3, 5 i 6. Karol zapisuje miasto dopiero wtedy, gdy już nie może z niego przejść do nowego miasta, bądź gdy wchodzi do miasta po raz drugi. W przykładzie kolejne miasta zapisane przez Karola to 1, 2, 3, 4, 6 i 5. Paweł postępuje jeszcze inaczej – zapisuje miasto dopiero wtedy, gdy jest w nim po raz ostatni. W przykładzie kolejne miasta zapisane przez Pawła to 1, 3, 2, 6, 5 i 4.

Napisz dwuparametrową funkcję opis, której wynikiem dla opisów trasy dokonanych przez Małgosię i Karola jest opis trasy dokonany przez Pawła. Opisy tras to listy zawierające numery odwiedzanych miast. Wynikiem funkcji jest lista zawierająca numery miast, sporządzona przez Pawła

opis [4 2 1 3 5 6] [1 2 3 4 6 5]jest [1 3 2 6 5 4]
opis [1 2 4 5 3 6 7] [4 2 5 1 6 3 7]jest [4 5 2 6 7 3 1]
opis [1 2 4 3] [4 2 1 3]jest [4 2 3 1]

Strategia

Lista Małgosi zawiera informacje dotyczące pierwszeg wejścia do miasta. Jednak skąd będzie wiadomo kiedy będziemy tam po raz ostatni? Otóż pewne jest, że do tego miasta wejdziemy po raz drugi jeśli gdziekolwiek ruszymy dalej. To gdzie ruszymy określa lista Karola. W pierwszym przykładzie wyruszamy z miasta 4. Które miasta odwiedzimy najpierw zanim wrócimy do miasta numer 4? Odpowiedzią jest każde miasto, które znajduje się na lewo od 4 na liście Karola. Ten fragment z kolei zostanie zastosowany do określenia drogi w dalszej części miasta.

Rozwiązanie

Rozwiązanie zadania odbywa się w sposób rekurencyjny. Jednak przed jej rozpoczęciem istnieje potrzeba utworzenia dwóch zmiennych globalnych: do przechowania aktualnej mapy Małgosi oraz zamienną zapisu wyniku. Jako jedyny argument przekazujemy mapę Karola.

  1. oto opis :m :k
  2.   przypisz "mapaMałgosia :m
  3.   przypisz "wynik []
  4.   opisrek :k
  5.   wy :wynik
  6. już

Z kolei w funkcji rekurencyjnej na początku (2.) sprawdzany jest warunek stopu, że na liście są miasta do odwiedzenia. Jeśli lista jest pusta to znaczy, że wycieczka będzie się cofać. Następnie (2.) pobierane jest kolejne miasto z mapy Małgosi i (3.) usuwamy je z mapy, ponieważ nie wejdziemy do tego miasta drugi raz po raz pierwszy.

  1. oto opisrek :lista
  2.   jeśli (długość :lista = 0) [ stop ]
  3.   niech "el pierw :mapaMałgosia
  4.   przyp "mapaMałgosia bp :mapaMałgosia
  5.   niech "poz numel :el :lista
  6.   niech "lewy []
  7.   powtórz (:poz - 1) [
  8.     niech "lewy nak pierw :lista :lewy
  9.     niech "lista bp :lista
  10.   ]
  11.   opisrek :lewy
  12.   niech "prawy bp :lista
  13.   opisrek :prawy
  14.   przypisz "wynik nak :el :wynik
  15. już

Dalsza część polega na (5.) przeszukaniu mapy Karola, aby (7. - 10.) dokonać podziału mapy na lewą i prawą stronę. Po odwiedzeniu (11.) lewej i (13.) prawej strony (14.) zapamiętany numer miasta można dopisać do wyniku. Warto zauważyć, że miasto początkowe jest zawsze miastem końcowym.

Zadanie 2 (iloczyny)

Ania bawi się liczbami z przedziału od 1 do 1 000 000. Każdą zapisuje jako iloczyn dwóch liczb, ale takich, których różnica jest możliwie najmniejsza. Napisz jednoparametrowa funkcję liczby, której parametrem jest lista liczb, a wynikiem odpowiadająca im lista par liczb (dwuelementowych list) utworzonych przez Anię. W każdej parze liczby zapisz tak, aby pierwsza nie była większa od drugiej

liczby [13 44 42]jest [[1 13][4 11][6 7]]
liczby [12 7 10 24]jest [[3 4][1 7][2 5][4 6]]
liczby [4 25 46 33]jest [[2 2][5 5][2 23][3 11]]

Strategia

W celu znalezienia odpowiedniej pary liczb dla danej liczby należy wpierw poszukać jej dzielników. Po znalezieniu dzielnika możliwe jest wyznaczenie drugiej liczby. Znając dwie liczby można wyznaczyć ich różnicę. Chociaż nie ma potrzeby wyróżniania takiego przypadku w zadaniu warto zauważyć, że dla pewnej liczby pierwszej n będzie odpowiadać para [1 n]..

Rozwiązanie

Zadanie można rozwiązać iteracyjnie. Na początek (2.) tworzona jest pusta lista i (3.) dla każdej liczby określamy zestaw instrukcji.

  1. oto liczby :lista
  2.   niech "w []
  3.   powtórz (długość :lista) [
  4.     niech "el element npw :lista
  5.     niech "a 1
  6.     niech "min -1
  7.     niech "p []
  8.     dopóki [:a <= :el/2][
  9.       jeśli (reszta :el :a = 0) [
  10.         niech "b :el/:a
  11.         niech "r abs(:b - :a)
  12.         jeśli (LUB (:r < :min) (:min = -1)) [
  13.           niech "min :r
  14.           niech "p (lista :a :b)
  15.         ]
  16.       ]
  17.       zwiększ "a
  18.     ]
  19.     niech "w nak :p :w
  20.   ]
  21.   wynik :w
  22. już

(4.) Pobierz element, (5.) a poszukiwania dzielnika rozpocznij od 1. (6.) Początkowo nie ma elementu minimalnego, a (7.) para znalezionych liczb jest pusta. (8.) Przeszukaj zakres [1, :el/2] w celu znalezienia wszystkich dzielników. (9.) Jeśli jest to faktycznie dzielnik to (10.) oblicz drugi wyraz i ich (11.) różnice. Jeśli (12.) wyliczona różnica jest mniejsza niż minimum lub minimum jest nie ustawione to (13. - 14.) zaktualizuj odpowiednio zmienne. Na koniec (19.) znalezioną parę należy dopisać na koniec wyniku i (21.) zwrócić wynik po wykonaniu pętli dla wszystkich liczb.

Zadanie 3 (strona)

Lista Antka zawiera informacje o wyświetleniach jego strony internetowej. Dla każdego wyświetlenia, w dwuelementowej liście pamiętane są dwie dane: moment wejścia i czas, jaki użytkownik spędził na stronie. Dane zapisywane są w pełnych sekundach.

Napisz jednoparametrową funkcję maxu, której parametrem jest lista Antka, a wynikiem maksymalna liczba użytkowników oglądających stronę Antka w tej samej sekundzie. Jako użytkownika oglądającego stronę w danej sekundzie, liczymy każdego, kto w tej sekundzie wchodzi na stronę, jest na niej od pewnego czasu, bądź w tej sekundzie przestaje ją oglądać

maxu [[1 2][2 2]]jest 2
maxu [[1 10][2 8][3 6]]jest 3
maxu [[1 2][2 3][1 10][2 2][5 5]]jest 4

Rozwiązanie

W celu rozwiązania tego zadania wpierw wszystkie wejścia zostaną posortowane względem czasu wejścia. Następnie pętla będzie wykonywana tak długo, aż wszystkie elementy zostaną obsłużone. W każdej iteracji z listy przenoszone są wszystkie elementy, których czas wejścia wynosi tyle co aktualny czas :i. Na listę u jest przenoszony jedynie czas jak długo dany użytkownik przebywał, ponieważ w każdej iteracji wartość ta będzie zmniejszana o 1, więc jeśli wyniesie 0 to zostanie usunięty z listy.

Rozwiązanie

Na początek inicjalizowanych jest kilka zmiennych: (2.) :i - aktualny czas, (3.) aktualna kolejka gości oraz (4.) aktualna maksymalna ilości gości tj. 0. (5.) Do listy na koniec został dołączony wartownik - jeśli będzie pierwszy to znaczy, że już nie ma więcej gości. Oczywiście informacje o gościach zostały posortowane.

  1. oto maxu :lista
  2.   niech "i 1
  3.   niech "u []
  4.   niech "max 0
  5.   niech "lista zd sortuj :lista "#
  6.   dopóki [pierw :lista <> "#][
  7.     dopóki [pierw pierw :lista = :i][
  8.       niech "u nak ost pierw :lista :u
  9.       niech "lista bp :lista
  10.     ]
  11.     jeśli (długość :u > :max) [
  12.       niech "max długość :u
  13.     ]
  14.     zwiększ "i
  15.     niech "p []
  16.     powtórz (długość :u) [
  17.       niech "el (element npw :u) - 1
  18.       jeśli (:el > 0) [
  19.         niech "p nak :el :p
  20.       ]
  21.     ]
  22.     niech "u :p
  23.   ]
  24.   wynik :max
  25. już

(6.) Dopóki są elementy na liście to (7. - 10.) przyjęcie wszystkich nowych gości, (11. - 13.) sprawdzenie czy nie ma nowej maksymalnej ich ilości. Jednak na koniec danego czasu :i (15. - 22.) należy wszystkim gościom zmniejszyć czas pobytu pozostały i tych którzy już wyszli usunąć ich z listy. Na koniec (24.) wystarczy zwrócić wartość zmiennej :max.

Zadanie 4 (robot)

Robot porusza się po kwadratowej planszy składającej się z n2 pól (n wierszy i n kolumn, 1 ≤ n ≤ 1 000). Na każdym polu może znaleźć się tylko raz. Jego początkowym kierunkiem jest kierunek „w prawo”. W każdym kolejnym ruchu robot stara się poruszać bez zmiany kierunku. Jeśli jest to niemożliwe (bo wyszedłby poza planszę lub wszedłby na pole już odwiedzone) – raz skręca w prawo o 90° i próbuje iść dalej. Jeśli jednak po skręcie nie może poruszyć się dalej (bo wyszedłby poza planszę lub wszedłby na pole już odwiedzone), to zatrzymuje się.

Napisz trzyparametrową funkcję lnp, której wartością jest liczba pól planszy, których robot nie odwiedzi. Pierwszy parametr n określa rozmiar planszy. Drugi i trzeci parametr (liczby od 1 do n) określają, odpowiednio, wiersz i kolumnę początkowego położenia robota.

lnp 4 1 2jest 4 (robot odwiedzi tylko pola znajdujące się przy krawędziach planszy)
lnp 4 3 1jest 8 (robot odwiedzi tylko pola znajdujące się w dwóch ostatnich wierszach planszy)
lnp 4 4 4jest 15 (robot nie wykona żadnego ruchu)

Strategia

Robot ma ograniczone pole przesuwania, więc możliwe jest utworzenie mapy planszy, a potem w trakcie działania algorytmu jej aktualizowanie. W momencie wykrycia, że robot wejdzie na już odwiedzone pole, albo wyjdzie poza plansze to automatycznie zostanie zwrócony wynik.

Rozwiązanie

Na początku działania programu można: (2.) utworzyć parę określającą aktualne położenie robota i (3. - 10.) utworzyć mapę.

  1. oto lnp :n :w :k
  2.   niech "p (lista :k :w)
  3.   niech "pola []
  4.   powtórz (:n) [
  5.     niech "px npw
  6.     powtórz (:n) [
  7.       niech "py npw
  8.       niech "pola nak (lista :px :py) :pola
  9.     ]
  10.   ]
  11.   niech "kier [[0 -1][1 0][0 1][-1 0]]
  12.   niech "cp [1 0]
  13.   dopóki [numel :p :pola > 0][
  14.     niech "pola bezElNum numel :p :pola :pola
  15.     niech "p :p + :cp
  16.     jeśli (lnp_poza :n :p) [
  17.       niech "p :p - :cp
  18.       niech "cp element ((reszta (numel :cp :kier) 4) + 1) :kier
  19.       niech "p :p + :cp
  20.       jeśli (lnp_poza :n :p) [
  21.         wynik długość :pola
  22.       ]
  23.     ]
  24.   ]
  25.   wynik długość :pola
  26. już

Mapa będzie to lista możliwych pól do odwiedzenia w postaci par współrzędnych (x, y). (11.) W celu uproszczenia metody przesuwania się deklarowana jest lista możliwych przesunięć robota. Kiedy robot będzie skręcać to zostanie cyklicznie wybrana kolejna wartość z tej zmiennej, a wybrana wartość zostanie przetrzymana (12.) w zmiennej :cp. (13.) Dopóki pole na którym znajduje się robot istnieje to (14.) usuwamy je z mapy i (15.) przesuwamy maszyne. (16.) Jeśli okaże się, że robot znalazł się poza planszą to (17.) robota jest przesuwany z powrotem (przesunięcie, które zostało dodane zostaje odjęte). Po powrocie należy (18.) zaktualizować przesunięcie i (19.) jeszcze raz powtórzyć przejście. Ważne jest, aby pamiętać, że po ponownym przejściu (20. - 22.) robot może znaleźć się poza planszą, więc należy ponownie sprawdzić odpowiedni warunek.

Sprawdzanie czy robot znajduje się poza planszą jest bardzo długim warunkiem, więc została utworzona specjalna funkcja lnp_poza, która na podstawie przekazanych wartości sprawdza czy robot wyszedł poza plansze czy nie.

  1. oto lnp_poza :n :p
  2.   wynik (LUB (LUB (pierw :p > :n) (pierw :p < 1))
  3.                         (LUB (ost :p > :n) (ost :p < 1)))
  4. już