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).

1. Piramida to ostrosłup, którego podstawa jest kwadratem, a boczne ściany to tójkąty równoboczne.
   Zlecono Ci pomalowanie bocznych ścian piramidy.
   Malując piramidę, możesz wziąć ze sobą wiaderko farby, które starcza na pomalowanie 1m² powierzchni, co trwa 1 minutę.
   Zarówno wejście na wysokość \(h\) metrów, jak i zejście na dół, trwają po \(\frac{h}{2}\) minut.
   Podstawa piramidy ma długość \(n\) metrów.
   Podaj, jakiego rzędu jest czas potrzebny do pomalowania całej piramidy.