Informatyka MIMUW

W poniższych zadaniach istotne jest posortowanie odpowiednich list:

1. Tomek ma zabawkę, z której wystają drewniane słupki różnej wysokości.
   Jednym uderzeniem młotka może wbić lub wysunąć wybrany słupek o 1.

   Napisz procedurę słupki : int list → int, która dla danej listy początkowych wysokości słupków
   obliczy minimalną liczbę uderzeń młotka potrzebnych do wyrównania wysokości słupków.

2. Napisz funkcję elementy : α list → int list → α list, która dla list $[x_1; x_2; \ldots, x_n]$ i
   $[y_1; y_2; \ldots; y_m]$ zwraca listę $[x_{y_1}; x_{y_2}; \ldots; x_{y_m}]$.
   Możesz założyć, że liczby całkowite $y_i$ w drugiej liście są z przedziału $[1, n]$, gdzie $n$ oznacza długość pierwszej listy.
3. [II OI]
   Napisz procedurę trójkąt : int list → bool, która dla danej listy $[x_1; x_2; \dots; x_n]$ dodatnich liczb
   całkowitych sprawdzi, czy taka lista zawiera trójkę elementów $x_i, x_j, x_k$ (dla $i \neq j$, $j \neq k$, $i \neq k$)
   spełniających nierówność trójkąta, tzn.:
   $$2 \cdot \max(x_i, x_j, x_k) \le x_i + x_j + x_k$$

   Podaj złożoność czasową i pamięciową swojego rozwiązania.
   (Uwaga: Jeżeli liczby całkowite mają ograniczony zakres, to można to zadanie rozwiązać w stałym czasie.)

4. Napisz procedurę przedział : int list → int → int, która dla danej listy $[x_1;\dots; x_n]$, oraz dla liczby całkowitej
   $r \ge 0$ obliczy taką liczbę całkowitą $c$, że $\left| \left\{i : |x_i - c| \le r \right\}\right|$ jest maksymalne.

   Przykład: przedział [2; -2; 5; -1; 11; 8; 4; 5; 8; 7] 2 = 6.
   
   Rozwiązania

5. Dana jest lista liczb rzeczywistych $[x_1; x_2; \dots; x_n]$.
   Napisz procedurę przekładaniec, której wynikiem jest taka permutacja $[x_{p_1}; x_{p_2}; \dots; x_{p_n}]$ danej listy,
   dla której suma
   $$\sum_{i=1}^{n-1} |x_{p_{i+1}} - x_{p_i}|$$
   jest największa.
   
   Rozwiązania
6. [*]
   Dana jest lista liczb całkowitych $[x_1; \dots; x_n]$.
   Napisz procedurę pierwsze : int list → int list, która zwróci taką jej spójną podlistę, że:
   • każde dwa elementy podlisty są względnie pierwsze,
   • zawiera ona maksymalną możliwą liczbę elementów.