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

Logia 2010/11 Etap III

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

Zadanie 1 (pionek)

Dużą sześcienną kostkę podzielono na 27 małych kostek, z których 25 jest białych, a 2 czerwone. Pionek może poruszać się we wnętrzu dużej kostki, w każdym ruchu przeskakując pomiędzy środkami sąsiednich (tj. stykających się ścianami) małych kostek.

Napisz funkcję PIONEK :s, która dla kostki opisanej daną :s, wyliczy minimalną liczbę ruchów, jaką musi wykonać pionek, aby pokonać drogę pomiędzy czerwonymi kostkami. Dana :s to słowo o długości 27, złożone z liter b (biała kostka) oraz c (czerwona kostka). Kolejne litery opisują kostki zgodnie z numeracją na rysunku.

PIONEK "cbbbbbbbbbbbbbbbbbbbbbbbbbcjest 6
PIONEK "bbbbbbbbbbbbbbbbbbbcbbbbbbcjest 3

Strategia

Dla każdego punktu na kostce można przypisać współrzędne na których znajduje się dany element. Posiadając współrzędne obydwu czerwonych kostek w postaci (x, y, z) odległość będzie można obliczyć ze wzoru: d = |x1 - x2| + |y1 - y2| + |z1 - z2|.

Rozwiązanie

Wszystkie punkty są zapisywane na (2.) listę pkty. Każdy z nich znajdowany jest poprzez (3. - 15.) mechanizm pętli. Przechodzi ona po wszystkich elementach kostki i sprawdza czy na liście dany element odpowiada czerwonemu elementowi. (10.) Jeśli tak to (11.) dopisywany jest na listę.

  1. oto PIONEK :s
  2.   niech "pkty []
  3.   powtórz 3 [
  4.     niech "z npw - 1
  5.     powtórz 3 [
  6.       niech "y npw - 1
  7.       powtórz 3 [
  8.         niech "x npw - 1
  9.         jeśli ((element :z*9+:y*3+:x+1 :s) = "c)[
  10.           niech "pkty nak (lista :x :y :z) :pkty
  11.         ]
  12.       ]
  13.     ]
  14.   ]
  15.   niech "w 0
  16.   niech "el1 pierw :pkty
  17.   niech "el2 ost :pkty
  18.   powtórz 3 [
  19.     niech "w :w + abs((element npw :el1) - (element npw :el2))
  20.   ]
  21.   wynik :w
  22. już

Dalsza część polega na (16.) inicjalizacji sumy odległości na 0. Następnie pobraniu (17.) pierwszego i (18.) ostatniego punktu. Potem (19. - 21.) dla każdej współrzędnej wyliczana jest odległość. Jest to ogólniejszy zapis wzoru podanego w strategii rozwiązania. Na koniec oczywiście należy zwrócić (22.) wynik.

Zadanie 2 (kostka)

Kilka osób gra z użyciem sześciennej kości. Gra składa się z kolejnych rund, w każdej rundzie każdy rzuca kością i zapisuje swój wynik. Gra kończy się po zakończeniu rundy, w której ktoś wyrzuci szóstkę. Ten, kto wyrzucił szóstkę, wygrywa. Jeśli więcej niż jeden gracz wyrzucił szóstkę, to wygrywa ten z nich, którego suma oczek we wszystkich rozegranych rundach jest największa. Jeśli takich graczy jest więcej, to rozgrywają oni kolejne dogrywki, zgodnie z zasadami określonymi w grze, aż do wyłonienia zwycięzcy.

Napisz funkcję KOSTKA :gra, której wynikiem jest imię zwycięzcy. Dana :gra jest listą dwuelementowych list opisujących grę (z ewentualnymi dogrywkami). Każda dwuelementowa lista składa się z imienia gracza i słowa zawierającego liczby oczek uzyskane w kolejnych rundach (tj. ciągu cyfr, w którym występują cyfry od 1 do 6).

KOSTKA [[Danka 555][Andrzej 236116][Marek 326336616][Adam 416516636][Karol 416126] [Grzesio 1461564][Krzysio 342]]jest "Adam

(Danka i Krzysio odpadli po trzeciej rundzie, Andrzej i Karol po szóstej, Grzesio po siódmej, a Marek i Adam grali do końca - w sumie trzy dogrywki, suma oczek Adama była większa niż suma oczek Marka)

Rozwiązanie

W przedstawionym zadaniu najpierw warto jeszcze raz przeczytać jaki jest cel zadania. Znaleziony ma zostać zwycięzca, który jest pewne, że gra do ostatniej rundy. Oznacza to, że najpierw należy znaleźć wszystkich graczy, którzy byli w grze do ostatniej rundy. Dopiero po tym wśród wszystkich pozostałych graczy trzeba znaleźć tego co ma największą sumę oczek.

Rozwiązanie

Na początek szukane są osoby, które zostały do ostatniej rundy. Zapisywane są one do (2.) listy osoby, a (3.) zmienna :max określa do której rundy dostały się osoby z listy. (4.) W pętli przechodząc po każdym graczu: (5.) pobieramy zapis jego rozgrywki, a następnie (6.) jeśli dotarł do dalszej rundy niż aktualnie przechowywane osoby to (7.) zmieniamy maksymalną rundę oraz (8.) czyścimy listę. Potem każdą osobę, która (9.) dotarła do aktualnie maksymalnej rundy (10.) jest dopisywana na listę.

  1. oto KOSTKA :gra
  2.   niech "osoby []
  3.   niech "max 0
  4.   powtórz (długość :gra) [
  5.     niech "el element npw :gra
  6.     jeśli (:max < długość ost :el) [
  7.       niech "max długość ost :el
  8.       niech "osoby []
  9.     ]
  10.     jeśli (:max = długość ost :el) [
  11.       niech "osoby nak :el :osoby
  12.     ]
  13.   ]
  14.   niech "zwyciezca "
  15.   niech "max 0
  16.   powtórz (długość :osoby) [
  17.     niech "el element npw :osoby
  18.     niech "suma 0
  19.     powtórz (długość ost :el) [
  20.       niech "suma :suma + element npw ost :el
  21.     ]
  22.     jeśli (:max < :suma) [
  23.       niech "zwyciezca pierw :el
  24.     ]
  25.   ]
  26.   wynik :zwyciezca
  27. już

Dalsza część polega już na znalezieniu zwycięzy. Domyślnie (13.) nie wygrał nikt i (14.) początkowo maksymalna ilość punktów to 0. Potem (15.) dla każdej osoby: (16. - 19.) liczymy sumę punktów i (20. - 22.) sprawdzamy czy nie jest to największy wynik. Na koniec (24.) zwracamy znalezionego zwycięzce.

Zadanie 3 (zgadnij)

Małgosia powiedziała na głos pewną liczbę i pomyślała o drugiej, która na pewno jest mniejsza. Obie liczby są całkowite dodatnie. Jaś próbuje zgadnąć tę liczbę, którą pomyślała Małgosia. Także mówi na głos liczbę i pyta Małgosię, czy to ta liczba. Na każde pytanie Małgosia udziela jednej z trzech odpowiedzi: moja liczba jest mniejsza, moja liczba jest większa, bądź moja liczba jest równa. Dodatkowym utrudnieniem jest założenie, że Małgosia raz może udzielić nieprawidłowej odpowiedzi. Jaś i Małgosia postanowili zapisywać przebieg gry w postaci listy dwuelementowych list - pierwszy element pary to liczba, jaką podaje Jaś, drugi to odpowiedź Małgosi - odpowiednio litera m, w, bądź r.

Napisz funkcję JAKIE :max :pytania, gdzie dana :max to liczba wypowiedziana przez Małgosię, a :pytania to lista opisująca przebieg gry. Wynikiem funkcji jest lista przedziałów, w których może wystąpić liczba pomyślana przez Małgosię. Powinna ona być możliwie najkrótsza i uporządkowana rosnąco.

JAKIE 10 [[5 m][2 w][4 m][1 w]] jest [[2 4]]
JAKIE 10 [[5 m][2 w][1 w][6 r]] jest [[3 4][6 6]]

Rozwiązanie

Początkowo warto napisać funkcję, która będzie umiała ciąg pytań i odpowiedzi zamienić na wynikający z tego zakres. Poniżej została przedstawiona przykładowa implementacja:

  1. oto JAKIE_ZAKRES :pytania :min :max
  2.   pokaż :pytania
  3.   powtórz (długość :pytania) [
  4.     niech "el element npw :pytania
  5.     wybierz (ost :el) [
  6.       m [
  7.             jeśli((pierw :el) - 1 < :max) [
  8.               niech "max (pierw :el) - 1
  9.             ]
  10.           ]
  11.       w [
  12.             jeśli((pierw :el) + 1 > :min) [
  13.               niech "min (pierw :el) + 1
  14.             ]
  15.           ]
  16.       r [
  17.             niech "min pierw :el
  18.             niech "max pierw :el
  19.           ]
  20.     ]
  21.   ]
  22.   pokaż (lista :min :max)
  23.   wynik (lista :min :max)
  24. już

Teraz kolejnym etapem jest utworzenie listy zakresów wynikających z podanych danych. W zadaniu zostało podane, że Malgosia może raz skłamać. Czyli należy sprawdzić jaki zakres wynika, gdy ani razu nie skłamała oraz :n przypadków bez jednego pytania, gdzie :n to ilość pytań na liście wejściowej. Potem znalezione zakresy będzie trzeba połączyć tak, aby było ich jak najmniej na liście.

  1. oto JAKIE :max :pytania
  2.   niech "zakresy []
  3.   niech "zakresy nak JAKIE_ZAKRES :pytania 1 :max :zakresy
  4.   powtórz (długość :pytania) [
  5.     niech "pytaniabe bezElNum npw :pytania
  6.     niech "w JAKIE_ZAKRES :pytaniabe 1 :max
  7.     jeśli (numel :w :zakresy = 0) [
  8.       niech "zakresy nak :w :zakresy
  9.     ]
  10.   ]

(2.) Przygotuj się do zapamiętania znalezionych zakresów i (3.) załóż, że Małgosia ani razu nie skłamała. Następnie w pętli (4.) odrzując jedno, kolejne pytania z listy (5.) wylicz zakres i (6.) jeśli dany zakres jeszcze nie istnieje na liście to (7.) go dopisz.

  1.   niech "zakresy sortuj :zakresy
  2.   niech "wynik []
  3.   niech "min pierw pierw :zakresy
  4.   niech "max ost pierw :zakresy
  5.   powtórz ((długość :zakresy) - 1) [
  6.     niech "el element (npw + 1) :zakresy
  7.     jeżeli (I (pierw :el >= :min) (pierw :el <= :max)) [
  8.       jeśli (ost :el > :max) [
  9.         niech "max ost :el
  10.       ]
  11.     ][
  12.       niech "wynik nak (lista :min :max) :wynik
  13.       niech "min pierw :el
  14.       niech "max ost :el
  15.     ]
  16.   ]
  17.   niech "wynik nak (lista :min :max) :wynik
  18.   wynik :wynik
  19. już

Dalsz część polega na (10.) posortowaniu znalezionych zakresów, (11.) przygotowania nowej pustej listy i (12. - 13.) zapamiętania pierwszego zakresu jako aktualna para min × max. Nastepnie (14.) dla każdego zakresu: (15.) pobierz kolejny zakres. Jeżeli (16. - 20.) kolejny zakres z poprzednim nachodzą na siebie to je połącz. W innym przypadku (20. - 24.) aktualną parę dopisz do wyniku, a potem nowy zakres ustal jako aktualną parę min × max. Przed zwróceniem wyniku (26.) należy pamiętać, że para min × max przechowuje jeszcze ostatni zakres, który trzeba dopisaćdo wyniku.

Zadanie 4 (wycieczka)

Ola wybrała się na wycieczkę w góry. Na szczyt, który postanowiła zdobyć, prowadzi wiele dróg przechodzących przez różne polany. Na polanach drogi mogą się krzyżować. Na każdej polanie, a także w dolinie, z której Ola rozpoczyna wędrówkę, stoją drogowskazy z nazwą polany pośredniej (lub szczytu, jeśli jest bezpośrednie wejście na szczyt) oraz czasem przejścia danego fragmentu drogi. Janek postanowił obliczyć, w jakim czasie najszybciej Ola jest w stanie wejść na szczyt. Oznaczył dolinę literą d, szczyt literą s, natomiast polany literą p z kolejnymi numerami. Informacje z drogowskazów zapisywał w postaci list trójelementowych [odMiejsca doMiejsca czasPrzejścia]. Na przykład [p1 p5 30] oznacza, że z polany p1 można przejść bezpośrednio na polanę p5 w czasie 30 minut.

Napisz funkcję DROGA :drogowskazy, której wartością jest minimalny czas wędrówki Oli. Dana :drogowskazy jest listą list opisujących poszczególne drogowskazy. Zakładamy, że istnieje co najmniej jedna droga na szczyt. Ola nie błądzi, czyli nie ma drogowskazów, które kierują w kółko przez te same polany.

DROGA [[d p1 10][d p2 20][p1 p3 20][p2 p3 5][p2 s 30][p3 s 5]]jest 30

(Najszybsza droga prowadzi przez polany p2 i p3 - 20+5+5. Przez polany p1 i p3 czas wynosi 35, a tylko przez polanę p2 - 50)

Strategia

Ze względu na fakt, że na trasie nie występują pętle to zadanie można rozwiązać przy pomocy rekurencji. Mianowicie w każdej iteracji funkcja sprawdzi, gdzie z danego miejsca może wyruszyć, a następnie zasymuluje przejście i wywoła samą siebie, aż nie dojdzie do celu trasy. Po dojściu wszystkie czasy zostana zsumowane, a program stwierdzi na tej podstawie, która trasa była najszybsza.

Rozwiązanie

Utwórzmy funkcje DROGA_REK, która będzie przyjmowała dwa argumenty: :gdzie - aktualna pozycja na trasie oraz :drogowskazy - mapa możliwych przejść.

  1. oto DROGA_REK :gdzie :drogowskazy
  2.   niech "min -1
  3.   powtórz (długość :drogowskazy) [
  4.     niech "el element npw :drogowskazy
  5.     jeśli(pierw :el = :gdzie) [
  6.       niech "w ost :el
  7.       jeśli (element 2 :el <> "s) [
  8.         niech "w :w + DROGA_REK element 2 :el :drogowskazy
  9.       ]
  10.       jeśli (LUB (:min = -1) (:w < :min)) [
  11.         niech "min :w
  12.       ]
  13.     ]
  14.   ]
  15.   wynik :min
  16. już

(2.) Początkowo czas przejścia jest nieokreślony. Potem (3.) dla każdego przejścia z drogowskazów: (4.) pobieramy każdy kolejny element. (5.) Jeśli dotyczy on przejścia z aktualnej pozycji to (6.) pobieramy cel i (7. - 9.) o ile nie prowadzi to do szczytu to (8.) szukamy dalej drogi. W przeciwnym razie (10.) sprawdzamy czy czas przejścia jest krótszy czy nie, albo niezdefiniowany i jeśli tak jest to (11.) przypisujemy znaleziony czas jako minimalny. Na koniec (15.) zwracamy znaleziony minimalny czas.

Teraz w głównej funkcji DROGA wystarczy wywołać DROGA_REK podając skąd się startuje i jakie są możliwe przejścia.

  1. oto DROGA :drogowskazy
  2.   wynik DROGA_REK "d :drogowskazy
  3. już