Ćwiczenia 21 i 22: Spamiętywanie i programowanie dynamiczne

  1. Jaka jest minimalna liczba monet lub banknotów potrzebna do wydania \(n\)zł reszty, przyjmując, że w obrocie są dostępne monety o zadanych (w postaci tablicy) nominałach?
  2. Na ile sposobów można wydać \(n\) zł reszty przyjmując, że w obrocie są dostępne monety o zadanych (w postaci listy) nominałach.
  3. Dana jest kwota \(k\) oraz zestaw nominałów banknotów \(b = [b_1; b_2; \dots; b_n]\).
    Mamy dowolną liczbę banknotów każdego z nominałów.
    Napisz procedurę \(\mathtt{banknoty}: \mathtt{int} \to \mathtt{int~list} \to \mathtt{int}\), która dla danych \(k\) i \(b\) obliczy minimalną liczbę różnych nominałów banknotów jakich należy użyć do wydania kwoty \(k\).
    Jeżeli nie da się wydać kwoty \(k\) używając podanych nominałów, to procedura powinna zwrócić -1.
    Na przykład, \(\mathtt{banknoty}\ 49\ [10, 15, 11, 12, 20] = 3\).
    Liczbę 49 można uzyskać na dwa sposoby: \(49 = 12 + 12 + 10 + 15 = 11 + 11 + 15 + 12\).
  4. [XII OI, zadanie Banknoty]
    W bankomacie znajdują się banknoty o nominałach \(b_1, b_2,\dots, b_n\), przy czym banknotów o nominale \(b_i\) jest w bankomacie \(c_i\).
    Jak wypłacić zadaną kwotę używając jak najmniejszej liczby banknotów?
  5. Antyczny bardzo długi kijek został połamany na kawałki. Należy go skleić.
    Wszystkie kawałki zostały już ułożone w odpowiedniej kolejności, ale nie wiadomo ile potrzeba kleju.
    Długości kolejnych kawałków są dane w postaci listy \(l=[x_1;x_2;\dots;x_n]\).
    Do slejenia kawałków długości \(a\) i \(b\) potrzeba \(\max(a,b)\) ml kleju.
    Po ich sklejeniu otrzymujemy jeden kawałek długości \(a+b\).

    Napisz procedurę klej : int list → int, która na podstawie długości
    kawałków obliczy minimalną ilość kleju (w ml) potrzebną do sklejenia wszystkich kawałków.

  6. [XII OI, zadanie Autobus]
    Ulice miasta tworzą szachownicę -- prowadzą z północy na południe, lub ze wschodu na zachód, a każda ulica prowadzi na przestrzał przez
    całe miasto -- każda ulica biegnąca z północy na południe krzyżuje się z każdą ulicą biegnącą ze wschodu na zachód i vice versa.
    Ulice prowadzące z północy na południe są ponumerowane od 1 do \(n\), w kolejności z zachodu na wschód.
    Ulice prowadzące ze wschód na zachód są ponumerowane od 1 do \(m\), w kolejności z południa na północ.
    Każde skrzyżowanie \(i\)-tej ulicy biegnącej z północy na południe i \(j\)-tej ulicy biegnącej ze wschodu na zachód
    oznaczamy parą liczb \((i, j)\) (dla \(1 \le i \le n\), \(1 \le j \le m\)).

    Po ulicach miasta kursuje autobus. Zaczyna on trasę przy skrzyżowaniu \((1, 1)\), a kończy przy skrzyżowaniu \((n, m)\).
    Ponadto autobus może jechać ulicami tylko w kierunku wschodnim i/lub północnym.

    Przy niektórych skrzyżowaniach znajdują się pasażerowie oczekujący na autobus.
    Rozmieszczenie pasażerów jest dane w postaci prostokątnej tablicy a \(n \times m\) liczb całkowitych --
    \(a.(i-1).(j-1)\) oznacza liczbę pasażerów czekających przy skrzyżowaniu \((i,j)\).

    Napisz procedurę autobus, która na podstawie tablicy a obliczy maksymalną liczbę pasażerów, których może zabrać autobus.
    Zakładamy, że w autobusie zmieści się dowolna liczba pasażerów.

  7. Mamy dany (w postaci listy) ciąg dodatnich liczb całkowitych \([x_1; x_2; \dots; x_n]\).
    Na ciągu tym można wykonywać operacje ,,sklejania'', tzn. dwa kolejne elementy ciągu można zastąpić jednym, równym ich sumie.
    Napisz procedurę: sklejanie : int list → int obliczającą minimalną liczbę operacji ,,sklejania'', które należy wykonać, aby ciąg był rosnący.
    Na przykład, sklejanie [3; 5; 4; 2; 7] = 1.

    Równoważne zadanie pojawiło się na konkursie USACO Open Gold w 2009\,r. i zostało opisane w
    Delcie.

  8. Na rozgałęzieniach drzewa siedzą wróble.
    Każde rozgałęzienie drzewa waży 1 kilogram, a nieujemna waga siedzących na tym rozgałęzieniu wróbli podana jest w drzewie:

     
          type drzewo = Leaf | Node of int * drzewo * drzewo
     

    Waga drzewa to suma wag rozgałęzień i siedzących na nich wróbli.
    Drzewo nazwiemy zrównoważonym, jeśli w każdym rozgałęzieniu waga dwóch poddrzew będzie taka sama.
    Rzucając celnie kamieniem w rozgałęzienie drzewa możemy przegonić wszystkie wróble z poddrzewa zaczepionego w tym rozgałęzieniu.
    Napisz funkcję rownowaga : drzewo → bool, która dla danego drzewa określa, czy da się tak rzucać kamieniami w drzewo,
    aby stało się ono zrównoważone. Podaj złożoność czasową i pamięciową swojego rozwiązania.

    Dla przykładu, aby zrównoważyć następujące drzewo:

     
          Node (3, Node (5, Node (1, Leaf, Leaf), Node (7, Leaf, Leaf)), Node (2, Leaf, Leaf))
     

    wystarczy raz rzucić kamieniem (w jego lewe poddrzewo).

  9. [XVI OI, zadanie Konduktor]
    Pociąg na trasie zatrzymuje się na \(n\) stacjach, ponumerowanych od 0 do \(n-1\).
    Dana jest tablica \(a\), taka że \(a.(i).(j)\) (dla \(0 \le i < j < n\)) jest równe liczbie pasażerów, którzy
    wsiadają na stacji \(i\) i wysiadają na stacji \(j\).
    Możesz wybrać \(k\) momentów (między kolejnymi stacjami), kiedy konduktor sprawdza bilety.
    Oblicz, jaka jest maksymalna liczba pasażerów, którym zostaną sprawdzone bilety.
  10. Dana jest dwuwymiarowa tablica \(a\) wypełniona nieujemnymi liczbami całkowitymi.
    Reprezentuje ona mapę prostokątnego lasu, a wartości tablicy odpowiadają liczbie drzew rosnących w różnych miejscach.
    Napisz procedurę prostokąt : int array → int → int, która dla zadanej tablicy \(a\) oraz liczby \(k\)
    znajdzie w obrębie tablicy (lasu) taki prostokąt, który:

    • zawiera przynajmniej \(k\) drzew, tzn.\ suma elementów tablicy w prostokącie jest \(\ge k\),
    • obwód prostokąta jest minimalny.

    Wynikiem procedury powinien być obwód tego prostokąta.
    Podaj złożoność czasową i pamięciową swojego rozwiązania.

    Prostokąt o dolnym lewym rogu \((x_1,y_1)\) i górnym prawym \((x_2,y_2)\) zawiera wszystkie elementy tablicy \(a.(i).(j)\) dla
    \(x_1 \le i \le x_2\), \(y_1 \le j \le y_2\), oraz ma obwód \(2 \cdot (x_2 - x_1 + 1) + 2 \cdot (y_2 - y_1 + 1)\).

  11. Dana jest prostokątna mapa złóż gazu. Mapa jest dana w postaci dwuwymiarowej prostokątnej tablicy nieujemnych liczb całkowitych, oznaczających ilość znajdującego się w danym miejscu gazu.
    Chcemy zakupić prawa do wydobywania gazu z terenu, który ma kształt prostokąta i zawiera łącznie przynajmniej \(k\) jednostek gazu.
    Napisz procedurę \(\mathtt{gaz}: \mathtt{int~array~array} \to \mathtt{int} \to \mathtt{int}\), która obliczy minimalną powierzchnię takiego terenu.
  12. Mamy most linowy długości\(N\) metrów (\(N \ge 1\)).
    Dla każdego metrowego odcinka mostu znamy jego wytrzymałość, to jest maksymalny ciężar jaki może znaleźć się łącznie na moście nie powodując rozerwania lin na tym odcinku.
    Możemy rozmieścić\(K\) podpór, dzieląc efektywnie most na\(K+1\) przylegających do siebie połączonych mostów.
    Podpory mają znikomą szerokość i rozmieszczamy je na styku metrowych odcinków mostu.

    Przed wjazdem na most zostaną ustawione dwa ograniczenia: maksymalny dopuszczalny ciężar pojazdu\(C\) jaki może wjechać na most, oraz minimalna odległość\(D\) jaką należy zachować między pojazdami.
    Jeśli dwie kolejne podpory znajdują się w odległości\(X\), to odcinki łączącego je mostu muszą mieć wytrzymałość przynajmniej \(\lceil \frac{X}{D}\rceil \cdot C\).

    Ograniczenie\(C\) będzie równe minimalnej wytrzymałości całego mostu.
    Twoim zadaniem jest wyznaczenie minimalnej możliwej wartości ograniczenia\(D\), jakie można uzyskać odpowiednio rozmieszczając podpory.
    Napisz procedurę\(\mathtt{most}: \mathtt{int~array} \to \mathtt{int} \to \mathtt{int}\), która mając dane wytrzymałości odcinków mostu oraz liczbę podpór\(K\) wyznaczy minimalną możliwą wartość ograniczenia\(D\).

  13. [XV OI, zadanie Kupno gruntu]
    Dana jest kwadratowa tablica \(n \times n\) nieujemnych liczb całkowitych \(a\), oraz dodatnia liczba całkowita \(k\).
    Napisz procedurę prostokat : int array array → int → (int * int) * (int * int), która dla tablicy \(a\) i
    liczby \(k\) znajdzie taki prostokątny obszar w obrębie tej tablicy, że suma liczb z tego obszaru jest między \(k\), a \(2k\).
    Ściśle mówiąc, jeśli \(\mathtt{prostokat}\ a\ k = ((x_1,y_1), (x_2, y_2))\), to \(k \le \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a.(i).(j) \le 2k\).
    Możesz założyć, że taki obszar istnieje.
  14. [BOI'2003, przeformułowane]
    Tomcio chce zrobić model drzewa (acyklicznego nieskierowanego grafu spójnego) z nitki i szklanych koralików i to taki,
    w którym koraliki tego samego koloru nie sąsiadują ze sobą.
    Nitkę już ma, ale koraliki musi kupić za swoje kieszonkowe.
    Ceny koralików różnych kolorów są różne, dla każdego dodatniego całkowitego \(n\) w sprzedaży są koraliki
    jednego koloru w cenie \(n\)\,gr za koralik.
    Tomcio zastanawia się z jakich koralików zrobić model drzewa, tak aby wydać jak najmniej.

    Opis drzewa ma postać struktury listowej, w której każdy węzeł to lista jego synów.
    Napisz procedurę koraliki, która na podstawie opisu drzewa obliczy minimalny koszt koralików
    potrzebnych do wykonania jego modelu.

    Uwaga: Dwa kolory wystarczą do wykonania modelu, ale nie dają minimalnego kosztu.
    Możesz założyć, że optymalna liczba kolorów nie przekracza \(\log_2 n\), gdzie \(n\) to liczba koralików.

  15. [IX OI, zadanie ,,Waga'']
    Dany jest zestaw odważników.
    Czy można na szalkach wagi położyć część odważników tak, żeby waga nadal była zrównoważona?
    Jeśli tak, to jaki najcięższy odważnik można przy tym użyć?
  16. [IX OI, zadanie ,,Nawiasy'']
    Dane jest wyrażenie postaci \(x_1 \pm x_2 \pm \dots \pm x_n\).
    Na ile różnych sposobów można uzyskać wyrażenie równoważne danemu wstawiając nawiasy do wyrażenia \(x_1 - x_2 - \dots - x_n\)?
    Uwaga: wstawiamy \(n-1\) par nawiasów w pełni określając kolejność wykonywania odejmowań.
  17. [XI OI, zadanie ,,Sznurki'']
    Interesują nas modele drzew (spójnych grafów acyklicznych) wykonane ze sznurka.
    Każde drzewo składa się z wierzchołków i pewnej liczby krawędzi łączących różne wierzchołki.
    Ten sam wierzchołek może być połączony z wieloma innymi wierzchołkami.
    Wierzchołki grafów mają być modelowane przez węzły zawiązane na kawałkach sznurka, a krawędzie przez odcinki sznurka pomiędzy węzłami.
    Każdy węzeł może być wynikiem zasuplenia kawałka sznurka lub związania w tym samym miejscu wielu kawałków.
    Każda krawędź ma długość 1. Długość sznurka użytego do zrobienia węzłów jest pomijalna.

    Chcemy zoptymalizować liczbę i długość kawałków sznurka użytych do wykonania modelu drzewa:

    • w pierwszym rzędzie należy zminimalizować liczbę potrzebnych kawałków sznurka,
    • zakładając, że liczba kawałków sznurka jest minimalna, należy zminimalizować długość najdłuższego kawałka sznurka.