Informatyka MIMUW

Rozwiązując poniższe zadania zwróć uwagę na efektywność algorytmów.
W większości zadań należy użyć techniki kosztu zamortyzowanego.

1. Napisz funkcję, która przekształci zadane drzewo w stóg, zachowując jego kształt (w rozwiązaniu można wykorzystać
   zmodyfikowaną procedurę rotate z wykładu).
   Jaka jest złożoność tej procedury? W jaki sposób zależy ona od kształtu drzewa?
2. Rozszerzyć implementację kolejek FIFO o wkładanie i wyjmowanie elementów z obydwu stron (w koszcie zamortyzowanym stałym).
3. Mamy $n$ kubeczków z wodą, ponumerowanych od 1 do $n$ ($n > 0$).
   W kubeczku nr $i$ znajduje się $x_i$ wody, przy czym $0 < x_1 \le x_2 \le \dots \le x_n$.
   Powtarzamy $k$ razy (dla $k < n$) nastepującą czynność:
   wybieramy dwa (niepuste) kubeczki zawierające jak najmniej wody i wodę z jednego kubeczka dolewamy do drugiego.

   Napisz procedurę $\mathtt{zlewki}:\mathtt{float~list} \to \mathtt{int} \to \mathtt{float}$,
   która dla danej listy zawierającej liczby $[|x_1; \dots; x_n|]$ oraz liczby $k$ określa
   określa ile jest wody w najmniej wypełnionym niepustym kubeczku po wykonaniu $k$ operacji przelewania.

4. Dana jest definicja typu reprezentującego pory roku: type pora = Wiosna | Lato | Jesień | Zima.
   Napisz procedurę $\mathtt{pory} : \mathtt{pora~array} \to \mathtt{int}$, która dla danego ciągu pór roku wyznaczy długość najkrótszego jej spójnego fragmentu, który zawiera podciąg złożony ze wszystkich czterech pór roku i to we właściwej kolejności.
   Jeżeli taki fragment nie istnieje, poprawnym wynikiem jest -1.
   Na przykład: pory [|Lato; Wiosna; Zima; Jesień; Lato; Zima; Wiosna; Jesień; Lato|] = 6.
   Fragment złożony z 6 ostatnich elementów danej tablicy zawiera podciąg: Jesień, Zima, Wiosna, Lato.
5. Zosia codziennie idąc do szkoły mija sadzawkę w parku i lubi ją obserwować. Zbliża się zima. W tej chwili na sadzawce nie ma lodu, ale wkrótce może się to zmienić. Jeżeli danego dnia temperatura jest ujemna i wynosi $-X^\circ$C, to górne $X$ mm wody na sadzawce zamarza. Jeżeli danego dnia temperatura jest dodatnia i wynosi $+X^\circ$C, to górne $X$ mm lodu topi się, o ile na sadzawce jest tyle lodu. Jeśli temperatura wynosi $0^\circ$C, to sadzawka się nie zmienia. Możesz założyć, że sadzawka nigdy nie zamarza do dna.

   Przykład: Poniżej podane są temperatury i czym będzie pokryta sadzawka (od góry) w kolejne dni:

   • $+2^\circ$C: nic,
   • $-12^\circ$C: 12 mm lodu,
   • $+8^\circ$C: 8 mm wody, 4 mm lodu,
   • $-4^\circ$C: 4 mm lodu, 4 mm wody, 4 mm lodu,
   • $+2^\circ$C: 2 mm wody, 2 mm lodu, 4 mm wody, 4 mm lodu,
   • $+4^\circ$C: 10 mm wody, 2 mm lodu – roztopiła się górna warstwa lodu i 2 mm dolnej warstwy,
   • $-4^\circ$C: 4 mm lodu, 6 mm wody, 2 mm lodu,
   • $+1^\circ$C: 1 mm wody, 3 mm lodu, 6 mm wody, 2 mm lodu,
   • $-3^\circ$C: 6 mm lodu, 4 mm wody, 2 mm lodu – zamarza górna warstwa lodu i 2 mm kolejnej warstwy wody.

   Napisz procedurę $\mathtt{sadzawka}: \mathtt{int~list} \to \mathtt{int~list}$, która dla danej listy temperatur zwróci listę reprezentującą kolejne warstwy pokrywające sadzawkę po tym okresie – liczby ujemne reprezentują lód, dodatnie wodę, a ich wartość bezwzględna grubość warstwy.
   Dla powyższego przykładu, poprawnym wynikiem jest $[-6, 4, -2]$.

6. Zadanie o katastrofach lotniczych:
   Dana jest lista liczb całkowitych$[x_1; \dots; x_n]$.
   Dla każdego $i$ trzeba policzyć największe takie $k_i$, że $x_i = \max (x_{i-k_i+1}, \dots x_i)$.
   Przyjmujemy, że $x_0 = \infty$.
7. Zaimplementuj $k$-max-kolejkę, czyli kolejkę, do której można wkładać elementy i dowiadywać się jakie jest maksimum
   z $k$ ostatnio włożonych elementów.
   Dokładniej, powinny być dostępne następujące operacje na $k$-max-kolejkach:
   • init : int → α max_queue -- tworzy nową pustą kolejkę z określonym parametrem $k$,
   • put : α max_queue → α → α max_queue -- wkłada element do kolejki,
   • get_max : α max_queue → α -- zwraca maksimum z $k$ ostatnich elementów włożonych do kolejki.

   Wszystkie operacje na kolejce powinny działać w stałym czasie zamortyzowanym.

8. Dana jest lista $[x_1; \dots; x_n]$ i stała $0 \le k < n$.
   Oblicz listę $[y_1; \dots; y_n]$, gdzie $y_i = \max(x_{\max(i-k,1)}, \dots, x_i)$.
9. Mamy daną listę liczb całkowitych $l = [a_1, \dots, a_n]$.
   Liczbę $a_i$ nazywamy $k$-maksimum, jeżeli jest ona większa od $a_{\max(i-k,1)}, \dots, a_{i-1}, a_{i+1}, a_{\min(i+k,n)}$.
   Napisz funkcję kmax : int → int list → int list, dla której wynikiem kmax $k$ $l$ jest podlista
   listy $l$ złożona z samych $k$-maksimów.
10. Dana jest lista $[x_1; \dots; x_n]$.
    Dla $1 \le i < j \le n$ powiemy, że elementy $x_i$ i $x_j$ widzą się nawzajem, jeżeli $\min(x_i, x_j) \ge \max(x_{i+1}, \dots, x_{j-1})$.
    Napisz procedurę widoczne, która obliczy ile elementów ciągu jest widocznych z kolejnych jego elementów.
    Np. widoczne [1; 8; 5; 6; 4] = [1; 3; 2; 3; 1].
11. Dana jest tablica $n$ dodatnich liczb całkowitych.
    Tablica ta opisuje figurę złożoną z $n$ stykających się bokami prostokątów-słupków, których dolne boki leżą na jednej prostej (tzw.~Manhattan skyline).
    Kolejne liczby w tej tablicy reprezentują wysokości kolejnych słupków jednostkowej szerokości(od lewej do prawej).

    Napisz procedurę \texttt{prostokat: int list → int}, która dla danej tablicy wyznaczy maksymalną powierzchnię prostokąta (o bokach równoległych do boków figury), który można wpisać w figurę opisaną przez tablicę.

12. [PCh]
    Dana jest lista liczb całkowitych $[x_1;\dots;x_n]$.
    Napisz procedurę różnica : int list → (int * int), która dla danej listy wyznaczy taką parę liczb $(i,j)$, że:
    • $0 < i < j \le n$,
    • $x_i \le x_j$, oraz
    • $j-i$ jest jak największe.

    Jeżeli takie $i$ i $j$ nie istnieją, to poprawnym wynikiem jest (0,0).

13. [SICP, Ćw 2.29]
    Mobil, to ruchoma konstrukcja o budowie rekurencyjnej.
    Mobil ma ruchome ramiona, jak w wadze szalkowej, określonej długości.
    Na końcu każdego z ramion zawieszony jest ciężarek o określonej masie, lub mniejszy mobil.
    • Zaimplementuj strukturę danych reprezentującą mobile.
    • Napisz procedurę obliczającą wagę mobila.
    • Napisz procedurę sprawdzającą, czy mobil jest wyważony.
    • [*] [BOI 1999 --- uproszczone]
      Napisz procedurę, która zrównoważy dany mobil tak, aby jego odważniki miały dodatnie wagi całkowite, a jego całkowita masa była minimalna.
14. [*][XII OI, zadanie Sumy Fibonacciego]
    System Zeckendorfa, to taki system, w którym liczba jest reprezentowana jako ciąg zer i jedynek, a kolejne cyfry mają
    takie znaczenie, jak kolejne liczby Fibonacciego ($1, 2, 3, 5, \dots$).
    Ponadto, w reprezentacji liczby nie mogą pojawiać się dwie jedynki obok siebie.

    Liczby reprezentujemy jako listy zer i jedynek.
    Zaimplementuj dodawanie w systemie Zeckendorfa.