Zadania trzeciego etapu Mazowieckiego Konkursu Informatycznego dla gimnazjalistów LOGIA 01, Logo i algorytmy

WPROWADZENIE - KRAINA WĘŻOWCÓW

Wężowce to sztuczne wyspy przytwierdzone do dna morskiego u wybrzeży oceanu.

Każdy wężowiec jest zbudowany z kwadratowych platform o wymiarach 10 m x 10 m.

Najprostszy wężowiec składa się z jednej platformy.
Złożony wężowiec jest ciągiem połączonych platform.
Pierwsza platforma w ciągu jest połączona (całym) jednym bokiem z drugą i tylko z nią, ostatnia - z przedostatnią i tylko z nią, a każda inna z dokładnie dwoma - poprzednią i następną.

Układy a i b na rysunku 1 to poprawnie zbudowane wężowce.

Układ c nie jest wężowcem, bo aż 4 platformy mają tylko jednego sąsiada, a 2 mają trzech sąsiadów.

Układ d nie jest wężowcem, bo tylko 1 platforma ma jednego sąsiada, a 3 mają trzech sąsiadów.

Kolonia wężowców może zajmować siatkę 20 x 20 pól, jak na rysunku 2.

Wężowce mogą przylegać do boków siatki, ale żadne dwa nie mogą się ze sobą stykać nawet rogami.

Pola siatki zajmowanej przez kolonię wężowców numerujemy kolejno od 0 do 399. Pola w wierszu najniższym na mapie mają kolejno od lewej do prawej numery od 0 do 19, pola w drugim od dołu wierszu mają numery od 20 do 39 itd. Pole w prawym górnym rogu mapy ma numer 399.

Opisem wężowca jest lista numerów wszystkich zajmowanych przez niego pól.

Kodem wężowca nazywamy taki opis, w którym:

  • każde dwie sąsiednie liczby na liście są numerami pól zajmowanych przez dwie sąsiednie platformy wężowca,
  • pierwsza liczba na liście jest mniejsza od ostatniej.

Każdy wężowiec, zajmujący co najmniej dwa pola ma wiele opisów różniących się porządkiem elementów, ale tylko jeden kod. Np. wężowiec w prawym dolnym rogu siatki na rysunku 2, składający się z 3 platform, ma 6 różnych opisów: [18 19 39] [19 39 18] itd., ale tylko jeden opis - [18 19 39] jest jego kodem.

Kolonie wężowców można kodować na wiele różnych sposobów. My przyjmujemy następujący system kodowania. Każdy wiersz siatki pól 20 x 20 pól zajmowanej przez kolonię opisujemy kolejno od góry do dołu za pomocą słów utworzonych z 20 cyfr binarnych 0 lub 1.

Opisem pierwszych 4 wierszy kolonii na rysunku 2 są odpowiednio słowa:

    00110000000000000000
    01100000000000001110
    11000000000001011010
    10000000111100010010

Każde takie słowo interpretujemy jako dwójkowy zapis liczby całkowitej i tłumaczymy na system dziesiętny. Otrzymana w ten sposób lista dwudziestu liczb jednoznacznie opisuje kolonię i jest jej kodem. Kodem kolonii przedstawionej na rysunku 2 jest lista: [196608 393230 786522 528146 125266 75858 338770 338240 339712 352256 262146 458874 3914 125258 76106 10570 125272 68352 122881 3].

Zadanie 1.

Zdefiniuj polecenie MAPA :kk, które mając dany kod kolonii wężowców :kk, rysuje na ekranie jej mapę, podobną do rysunku poniżej. Morze na mapie powinno być granatowe, a każdy wężowiec pomalowany na inny kolor. Zakładamy, że dana kolonia może się składać z co najwyżej 12 wężowców, więc 16 podstawowych kolorów zupełnie wystarczy. Uwaga: nie rysujemy linii siatki. Dla danego kodu kolonii przedstawionej na rysunku 2 we wprowadzeniu, mapa utworzona przez Twoją procedurę może się różnić od rysunku poniżej tylko wyborem kolorów, ale każdy wężowiec na mapie musi mieć inny kolor.

Poniższy rysunek przedstawia wywołanie MAPA [196608 393230 786522 528146 125266 75858 338770 338240 339712 352256 262146 458874 3914 125258 76106 10570 125272 68352 122881 3].

Zadanie 2.

Zdefiniuj funkcję ODBICIE :kw, która mając kod wężowca, daje w wyniku kod jego symetrycznego odbicia względem pionowej osi symetrii kwadratowej siatki pól.

Oto przykładowe wyniki:

ODBICIE [48 68 88 108 128 148 149 150 151 131 111 91 71 51 50]
powinno dać wynik [49 48 68 88 108 128 148 149 150 151 131 111 91 71 51],
ODBICIE [18 19 39]
powinno dać wynik [1 0 20].

Zadanie 3.

Zdefiniuj funkcję PROST :kw, która mając dany kod wężowca, znajduje minimalny prostokąt pól na mapie, w którym mieści się dany wężowiec. Wynikiem funkcji ma być lista dwóch nieujemnych liczb całkowitych: pierwsza - to numer pola w lewym dolnym rogu wyznaczonego prostokąta, a druga - to numer pola w prawym górnym rogu.

Oto przykładowe wyniki:

PROST [48 68 88 108 128 148 149 150 151 131 111 91 71 51 50]
powinno dać wynik [48 151],
PROST [22]
powinno dać wynik [22 22],
PROST [3 23 22 42 41]
powinno dać wynik [1 43].

Zadanie 4.

Zdefiniuj funkcję KODW :opis, która mając dany jakikolwiek opis wężowca, daje w wyniku jego kod.

KODW [48 50 51 68 71 88 91 108 111 128 131 148 149 150 151]
powinno dać wynik [48 68 88 108 128 148 149 150 151 131 111 91 71 51 50],
KODW [22]
powinno dać wynik [22],
KODW [22 3 42 41 23]
powinno dać wynik [3 23 22 42 41].