- [PCh, Zadanie o misjonarzach i kanibalach]
Przez rzekę chcą przeprawić się kanibale i misjonarze.
Kanibali i misjonarzy jest po trzech.
Mają jedną łódkę, którą może płynąć do dwóch osób.
Łódką umieją wiosłować kanibale i tylko jeden misjonarz.
Jeżeli w dowolnej chwili, na dowolnym brzegu rzeki będzie więcej kanibali, niż misjonarzy, to zjedzą oni misjonarzy.
W jaki sposób wszyscy mogą bezpiecznie przeprawić się na drugi brzeg.
- [PCh, Zadanie o trzech małżeństwach]
Przez rzekę chcą przeprawić się trzy małżeństwa.
Mają jedną łódkę, którą może płynąć do dwóch osób.
Każda z kobiet może pozostać na brzegu w obecności mężczyzn tylko, jeżeli jest wśród nich jej mąż.
W jaki sposób wszyscy mogą bezpiecznie przeprawić się na drugi brzeg?
- [CLR]
Minimalny koszt mnożenia n macierzy, o wymiarach \(x_1 \times x_2, x_2 \times x_3, \dots, x_n \times x_{n+1}\).
- [CLR 17.2-5]
Dany jest zbiór punktów na osi.
Podaj minimalną liczbę odcinków jednostkowych, jakimi można pokryć punkty z tego zbioru.
-
Rozważmy taką oto łamigłówkę:
Dana jest lista liczb całkowitych \(l = [x_1; x_2; \dots; x_n]\).
W jednym ruchu możemy wybrać dowolne dwa równe elementy listy, usunąć je i wstawić na koniec listy ich sumę.
Takie ruchy możemy powtarzać.
Jaka jest minimalna długość listy jaką można uzyskać?
Napisz procedurę \(\mathtt{lamiglowka} : \mathtt{int~list} \to \mathtt{int}\), która dla danej listy \(l\) wyznaczy minimalną długość listy jaką można uzyskać.
Na przykład, \(\mathtt{lamiglowka}\ [4; 3; 4; 5; 12; 2; 3; 1; 6; 1] = 4\).
-
Rozważmy taką oto łamigłówkę:
Dana jest lista dodatnich liczb całkowitych \(l = [x_1; x_2; \dots; x_n]\). W jednym ruchu możemy wybrać dowolne dwa różne elementy listy, usunąć je i wstawić na koniec listy wartość bezwzględną ich różnicy. Takie ruchy możemy powtarzać. Kończymy, gdy wszystkie elementy listy są sobie równe. Jaka jest minimalna wartość, jaką można na koniec uzyskać na liście?
Napisz procedurę \(\mathtt{lamiglowka} : \mathtt{int~list} \to \mathtt{int}\), która dla danej listy \(l\) wyznaczy minimalną wartość jaką można uzyskać.
-
W korytarzu harcują myszy. Korytarz ma długość \(n\) metrów.
Dana jest tablica \(n\) nieujemnych liczb całkowitych \(a\) opisująca gdzie jest ile myszy,
dokładnie na odcinku od \(i\) do \(i+1\) metrów od wejścia do korytarza jest \(a.(i)\) myszy.
Dysponujesz \(k\) kotami (\(k \le n\)).
Twoim zadaniem jest takie rozmieszczenie kotów w korytarzu, żeby złapały jak najwięcej myszy.
Każdy kot może pilnować ustalonego przez Ciebie spójnego fragmentu korytarza (na przykład, może mieć założoną smycz odpowiedniej długości, przymocowaną do podłogi pośrodku pilnowanego fragmentu korytarza).
Fragmenty korytarza pilnowane przez różne koty nie mogą zachodzić na siebie (żeby koty się nie pobiły a smycze nie poplątały), choć mogą się stykać.
Niektóre fragmenty korytarza mogą pozostać niepilnowane przez żadnego kota.
Kot, który pilnuje fragmentu korytarza od \(i\) do \(j\) metrów od wejścia (dla \(i < j\)), na którym znajduje się \(s = a.(i) + a.(i+1) + \cdots + a.(j-1)\) myszy, złapie: \(\max(s - (j-i-1)^2, 0)\) myszy.
Na przykład, dla \(k=2\) oraz \(a = [|1; 5; 1; 4; 3; 2; 7; 0|]\) poprawnym wynikiem jest 14, jeden kot może pilnować fragmentu korytarza od 1 do 4 metrów od wejścia (łapiąc 6 z 10 myszy), a drugi może pilnować fragmentu korytarza od 4 do 7 metrów od wejścia (łapiąc 8 z 12 myszy).
Napisz procedurę \(\mathtt{myszy}: \mathtt{int} \to \mathtt{int~array} \to \mathtt{int}\), która dla danej liczby \(k \ge 0\) oraz tablicy \(a\), wyznaczy maksymalną liczbę myszy, jakie złapią koty.
Rozwiązanie tego zadania zostało omówione w Delcie
-
Rozpatrujemy przedstawienia liczby naturalnej \(n\) jako sumy różnych składników nieparzystych, tzn. rozważamy takie ciągi \((x_1, \dots, x_k)\), że:
- \(1 \le x_i\) i \(x_i\) jest nieparzyste (dla \(i=1,\dots, k\)),
- \(x_1 > x_2 > \dots > x_k\),
- \(x_1 + \cdots + x_k = n\).
-
Napisz procedurę, która dla danej liczby \(n\) obliczy, na ile różnych sposobów można ją przedstawić jako sumę różnych nieparzystych składników.
Na przykład, dla \(n=2\) poprawnym wynikiem jest 0, a dla \(n=12\) poprawnym wynikiem jest 3.
-
Napisz procedurę, która dla danej liczby \(n\) wyznaczy (pewne) przedstawienie tej liczby jako sumy maksymalnej liczby nieparzystych składników.
Na przykład, dla \(n=42\) poprawnym wynikiem może być [15; 11; 7; 5; 3; 1].
-
Rozważamy ciągi liczb całkowitych \((x_1, x_2, \dots, x_k)\) konstruowane zgodnie z następującymi regułami:
- \(x_1 = 1\),
- \(x_{i+1} = x_i + 1\), lub
- \(x_{i+1} = x_i \cdot f_i\) dla pewnej liczby Fibonacciego \(f_i\).
Napisz procedurę \(\mathtt{ciag} : \mathtt{int} \to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\) wyznaczy najkrótszy taki ciąg \((x_1, x_2, \dots, x_k)\), że \(x_k = n\).
Na przykład \texttt{ciag 42} powinno zwrócić \([1; 2; 42]\) lub \([1; 21; 42]\).
-
Tworzymy ciąg liczb całkowitych \((x_k)\) w następujący sposób:
- \(x_0 = 1\),
- dla każdego \(k > 0\) wybieramy pewne \(0 \le i, j < k\) i przyjmujemy \(x_k = x_i + x_j\).
Napisz procedurę ciąg : int → int list, która dla danego \(n \ge 1\) znajdzie najkrótszy taki ciąg \(x_0, x_1, ..., x_k\), który spełnia powyższe warunki, oraz \(x_k = n\).
Wynikiem procedury powinna być lista \([x_0; ...; x_k]\).
-
Rozważamy ciągi liczb całkowitych \((x_1, x_2, \dots, x_k)\) konstruowane zgodnie z następującymi regułami:
- \(x_1 = 1\),
- \(x_{i+1} = x_i + 1\), lub
- \(x_{i+1} = x_i \cdot p_i\) dla pewnej liczby pierwszej \(p_i\).
Napisz procedurę \(\mathtt{ciag} : \mathtt{int} \to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\) wyznaczy najkrótszy taki ciąg \((x_1, x_2, \dots, x_k)\), że \(x_k = n\).
Możesz założyć, że dane są procedury:
- \(\mathtt{prime}:\mathtt{int}\to\mathtt{bool}\) sprawdzająca czy dana liczba jest pierwsza, oraz
- \(\mathtt{primes}:\mathtt{int}\to \mathtt{int~list}\), która dla danej dodatniej liczby całkowitej \(n\) zwraca listę liczb pierwszych nie przekraczających \(n\) (uporządkowaną rosnąco).
-
Dla danych dodatnich liczb całkowitych \(l\) i \(m\) szukamy przedstawienia ułamka \(\frac{l}{m}\), jako możliwie najkrótszej sumy odwrotności dodatnich liczb całkowitych: \[\frac{l}{m} = \frac{1}{s_1} + \frac{1}{s_2} + \cdots + \frac{1}{s_k}\]
Napisz procedurę rozklad : int * int → int list, która dla danych liczb \(l\) i \(m\) wyznaczy szukany ciąg mianowników \([s_1;\dots;s_k]\).
-
Dana jest dodatnia liczba całkowita \(x\).
Interesują nas różne rozkłady \(x\) na sumę różnych (dodatnich) liczb Fibonacciego.
Dwa rozkłady, które różnią się jedynie kolejnością składników uznajemy za takie same.
Tylko rozkłady, które mają inne zbiory składników uznajemy za różne.
Napisz procedurę \(\mathtt{rozklady} : \mathtt{int} \to \mathtt{int}\), która dla danej liczby \(x\)
policzy na ile różnych sposobów można przedstawić \(x\) jako sumę różnych (dodatnich) liczb Fibonacciego.
Na przykład \(\mathtt{rozklady}\ 42 = 6\).
-
Dana jest lista dodatnich liczb całkowitych \([x_1; x_2; \dots; x_n]\) oraz dodatnia liczba całkowita \(k\).
Napisz procedurę podzial : int list → int → int list list, która podzieli daną listę na \(k\) spójnych fragmentów
\([[x_1; \dots; x_{n_1}]; [x_{n_1+1}; \dots; x_{n_2}]; \dots; [x_{n_{k-1}+1}; \dots;x_n]]\) w taki sposób, że
\(\max \{x_1+ \cdots+ x_{n_1}, x_{n_1+1}+\cdots+ x_{n_2}, \dots, x_{n_{k-1}+1}+ \cdots+ x_n\}\) jest jak najmniejsze.
Jeżeli \(k > n\), to w liście wynikowej mogą występować puste listy.
Na przykład podzial [1; 4; 2; 2; 4; 1; 2; 4] 3 = [[1; 4; 2]; [2; 4]; [1; 2; 4]].
-
Na przystanku autobusowym pojawiają się pasażerowie czekający na autobus. O określonych godzinach podjeżdżają puste autobusy, do których mogą wsiadać pasażerowie. Należy obliczyć minimalną wielkość autobusów, pozwalającą na przewiezienie wszystkich pasażerów (wszystkie autobusy są tej samej wielkości).
Tablica \(p\) zawierająca \(n\) nieujemnych liczb całkowitych opisuje pojawianie się pasażerów, w chwili \(i\) na przystanek przychodzi \(p.(i)\) pasażerów.
Tablica \(a\) opisuje momenty przyjazdu autobusów na przystanek -- jest ona uporządkowana niemalejąco i zawiera liczby całkowite z zakresu od 0 do \(n\).
Napisz procedurę \(\mathtt{autobusy}: \mathtt{int~array} \to \mathtt{int~array} \to \mathtt{int}\), taką że \(\mathtt{autobusy}\ p\ a\) oblicza minimalną konieczną wielkość autobusów.
Jeżeli nie da się obsłużyć wszystkich pasażerów, to poprawnym wynikiem jest -1.
Na przykład, autobusy [|1; 0; 2; 1; 2; 0; 1; 2; 6; 0; 6; 0|] [|2; 6; 8; 11|] = 7}.
- [XVI OI, zadanie Słonie]
Dane jest tablica \(p\) długości \(n\) zawierająca permutację liczb ze zbioru \(\{0,\dots,n-1\}\).
Chcemy posortować tablicę \(p\) rosnąco, ale jedyną operacją modyfikującą, którą możemy wykonywać na niej jest zamiana zawartościami dwóch komórek o podanych indeksach.
Zamiana komórek zawierających liczby \(x\) i \(y\) kosztuje \(x+y+1\).
Napisz procedurę koszt : int array → int, która oblicza minimalny koszt posortowania tablicy \(p\).
- [II OI]
Dany jest zestaw \(n\) czynności.
Wykonanie każdej z tych czynności trwa tym dłużej, im później się ją zacznie, konkretnie jeżeli zaczniemy wykonywać czynność \(i\) w chwili \(t\), to jej wykonanie będzie trwać \(a_i t + b_i\).
Jaki jest minimalny czas wykonania wszystkich tych czynności, jeżeli zaczynamy je wykonywać w chwili 0?
-
Rozważamy drzewa postaci:
type expr =
NWD of expr * expr |
NWW of expr * expr |
Number of int
Drzewa takie reprezentują wyrażenia.
NWD oznacza największy wspólny dzielnik, a NWW najmniejszą wspólną wielokrotność dwóch podwyrażeń.
Argumentami Number są liczby nieujemne.
\(\mathtt{Number}\ x\), dla \(x>0\) oznacza liczbę \(x\).
\(\mathtt{Number}\ 0\) oznacza miejsce, w które należy wstawić dodatnią liczbę.
Napisz procedurę \(\mathtt{wstaw}: \mathtt{expr} * \mathtt{int} \to \mathtt{int}\), która dla danego drzewa \(t\) i dodatniej liczby całkowitej \(n\) znajdzie taką najmniejszą dodatnią liczbę całkowitą \(x\), że gdy wstawimy \(\mathtt{Number}\ x\) w miejsce wszystkich wystąpień \(\mathtt{Number}\ 0\) w \(t\), to wartością wyrażenia będzie \(n\).
Jeżeli taka liczba \(x\) nie istnieje, to poprawnym wynikiem jest 0.
Na przykład, dla \(t = \mathtt{NWW(NWW(Number 2, Number 0), NWD(Number 0, Number 49))}\) i \(n = 42\), \(\mathtt{wstaw}\ t\ n = 21\).
Rozwiązania
-
Przez park biegnie długa prosta alejka. Przy tej alejce, w określonych miejscach, znajduje się \(n\) ławeczek. Wzdłuż alejki chcemy zamontować \(k\) latarni. Dla każdej ławeczki interesuje nas odległość do najbliżej położonej latarni. Latarnie chcemy rozmieścić tak, żeby maksymalna odległość od ławeczki do najbliżej niej położonej latarni była jak najmniejsza, przy czym latarnie mogą być umieszczone tylko w miejscach o współrzędnych całkowitych.
Masz daną posortowaną tablicę $n$ liczb całkowitych określających położenie ławeczek oraz liczbę \(k\). Napisz procedurę \(\mathtt{latarnie}: \mathtt{int~array} \to \mathtt{int} \to \mathtt{int~array}\), która na ich podstawie wyznaczy gdzie należy postawić latarnie i zwróci posortowaną tablicę z ich pozycjami.
Na przykład, dla tablicy \([|-4; -3; -1; 2; 2; 3; 8; 10; 11|]\) oraz \(k=3\) jednym z możliwych wyników jest \([|-2; 2; 10|]\).
-
Dane jest drzewo typu:
type choinka =
Koniuszek |
Galaz of choinka |
Rozgalezienie of choinka * choinka;;
opisujące kształt choinki.
- [PCh]
W węzłach choinki (Rozgalezienie, Galaz i Koniuszek) możemy umieszczać świeczki.
Powiemy, że choinka jest oświetlona, jeżeli dla każdej krawędzi (łączącej węzły) choinki przynajmniej w jednym jej końcu znajduje się świeczka.
Napisz procedurę, która dla danej choinki obliczy minimalną liczbę świeczek potrzebnych do oświetlenia choinki.
- [PCh]
Na każdej krawędzi (łączącej węzły) choinki wieszamy jedną bombkę.
Mamy do dyspozycji trzy rodzaje bombek: czerwone po 2zł, niebieskie po 5zł i srebrne po 7zł.
Choinkę należy przystroić w taki sposób, żeby na krawędziach o końcach w tym samym węźle wisiały bombki o różnych kolorach, a łączny koszt przystrojenia całej choinki był jak najmniejszy.
-
W węzłach choinki (
Rozgalezienie, Galaz i Koniuszek) wieszamy bombki.
Dostępne są trzy rodzaje bombek:
- czerwone, wykonane z miedzi, każda taka bombka waży 1kg,
- srebrne, wykonane z białego złota niskiej próby, każda taka bombka waży 2kg,
- złote, wykonane ze szczerego złota, każda taka bombka waży 3kg.
Bombki należy zawiesić tak, aby choinka nie chwiała się, tzn. dla każdego rozgałęzienia łączny ciężar bombek
zawieszonych po lewej i po prawej stronie musi być taki sam.
Pytanie czy jest to możliwe, a jeżeli tak, to na ile sposobów?
Napisz procedurę, która dla danej choinki obliczy na ile sposobów można powiesić na niej bombki.