-
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?
-
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.
-
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\).
- [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?
-
Dana jest tablica zawierająca dostępne nominały monet i banknotów. Tablica ta zawiera dodatnie liczby całkowite i jest uporządkowana rosnąco.
Napisz procedurę \(\mathtt{unikat} : \mathtt{int~array} \to \mathtt{int} \to \mathtt{int}\), która dla danej tablicy nominałów i nieujemnej kwoty \(k\) zwróci największą taką kwotę, która: nie przekracza \(k\) i może być wydana w dokładnie jeden sposób.
Dwa sposoby wydania danej kwoty są różne, jeżeli mają różne multi-zbiory użytych nominałów.
-
Atomy bajtonium mają po \(k\) elektronów (\(k > 0\)). Elektrony w atomach bajtonium mogą znajdować się na \(n\) różnych powłokach, ponumerowanych od 0 do \(n-1\), przy czym na każdej powłoce może znajdować się co najwyżej jeden elektron. Masz daną tablicę \(t\), posortowaną niemalejąco, zawierającą liczby całkowite z zakresu od 0 do \(n^2\). Tablica ta opisuje energię elektronów znajdujących się na poszczególnych powłokach, to znaczy, elektron znajdujący się na powłoce \(i\) ma energię \(t.(i)\).
Napisz procedurę \(\mathtt{energia}: \mathtt{int} \to \mathtt{int~array} \to \mathtt{int} \to \mathtt{int~array}\), która na podstawie liczby \(k\), tablicy \(t\) oraz energii \(e\) wyznaczy orbity, na których powinny znajdować się elektrony w atomie bajtonium tak, żeby ich łączna energia wynosiła \(e\). Wynikiem powinna być tablica \(k\) numerów powłok z elektronami, uporządkowana rosnąco. Jeżeli uzyskanie danej energii nie jest możliwe, wynikiem powinna być pusta tablica (\([||]\)).
Przykład: wynikiem energia 4 [|2; 8; 12; 12; 20|] 42 powinno być [|0; 1; 2; 4|] lub [|0; 1; 3; 4|], natomiast energia 4 [|2; 8; 12; 12; 20|] 60 = [||].
-
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.
-
Dana jest tablica dodatnich liczb całkowitych \(t = [|x_1; x_2; \dots; x_n|]\). Spójny fragment tej tablicy \([|x_i; \dots; x_j|]\) nazwiemy segmentem Fibonacciego rzędu \(k\), jeżeli:
- \(i = j\) oraz \(x_i = x_j = k\), lub
- istnieje takie \(l\), \(i \le l < j\), że \([|x_i; \dots; x_l|]\) oraz \([|x_{l+1}; \dots; x_j|]\) są segmentami Fibonacciego rzędu \(k-1\) i \(k-2\) (w dowolnej kolejności).
Napisz procedurę \(\mathtt{segment}: \mathtt{int~array} \to \mathtt{int}\), która dla danej tablicy \(t\) wyznaczy największy rząd występującego w niej segmentu Fibonacciego.
Jeżeli nie występuje w niej żaden taki segment, to poprawnym wynikiem jest zero.
Przykład: segment [| 1; 3; 2; 3; 4; 5; 3; 6|] = 7. Segment Fibonacciego rzędu 7, to \([|3; 2; 3; 4; 5|]\) (\(Fib_7 = 13\)).
- [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.
- [VII OI, zadanie Jajka, zmodyfikowane]
Dostaliśmy \(k\) identycznych wytrzymałych strusich jaj. Okazuje się, że są one wytrzymałe na upadki z dużych wysokości. Mieszkamy w \(n\)-piętrowym wieżowcu.
Chcemy sprawdzić, jakie jest maksymalne piętro \(p\) (\(0\le p \le n\)), z którego jak zrzucimy strusie jajo, to się ono nie zbije.
Napisz funkcję \(\mathtt{liczba\_prob} : \mathtt{int} \to \mathtt{int} \to \mathtt{int}\) taką, że \(\mathtt{liczba\_prob}\ n\ k\) zwróci najmniejszą (pesymistycznie) liczbę prób zrzucania jaj potrzebną do wyznaczenia \(p\) mając do dyspozycji \(k\) jaj.
Inaczej mówiąc, szukamy takiej strategii wyznaczenia \(p\), która w najgorszym przypadku będzie wymagać jak najmniejszej liczby zrzucań jajek.
Uwagi:
- Jajo zbije się tylko wtedy, gdy zrzucamy je z piętra wyższego niż \(p\).
- Jeżeli jajo się zbije, to je tracimy. Jeśli nie, to można je użyć do kolejnej próby.
- Budynek ma \(n+1\) kondygnacji, wliczając parter.
- Jeżeli jajo zrzucone z parteru też się zbija, to poprawnym wynikiem jest \(-1\).
Na przykład: \(\mathtt{liczba\_prob}\ n\ 1 = n + 1\), \(~~\mathtt{liczba\_prob}\ 4\ 2 = 3\).
-
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.
-
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).
-
Każda latarnia jest opisana przez trójkę postaci \((x, y, p)\) oznaczającą, że latarnia może oświetlić (domknięty) odcinek alejki od \(x\) do \(y\) i pobiera wtedy \(p\)W energii elektrycznej (\(x < y, p> 0\)).
Dana jest lista trójek opisujących latarnie, oraz para liczb \((a, b)\), \(a < b\), opisująca odcinek alejki, który chcemy oświetlić.
Napisz procedurę \(\mathtt{moc}: (\mathtt{int} * \mathtt{int} * \mathtt{int})\ \mathtt{list} \to (\mathtt{int} * \mathtt{int}) \to \mathtt{int}\), która obliczy minimalną moc potrzebną do oświetlenia danego odcinka alejki. Jeżeli jego oświetlenie nie jest możliwe, to poprawnym wynikiem jest \(-1\).
Przykład:
moc [(2, 5, 10), (10, 12, 4), (-1, 2, 8), (6, 9, 10), (9, 15, 20),
(4, 7, 8), (0, 12, 100), (8, 10, 4), (-2, 2, 6)] (1, 11) = 42
- [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.
-
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)\).
-
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.
-
Zosia bardzo lubi czekoladę z orzechami, a im więcej orzechów tym lepiej. Mama pozwoliła Zosi zjeść jeden prostokątny kawałek czekolady składający się z dokładnie \(k\) kosteczek. Zosia wpatruje się w tabliczkę czekolady i zastanawia się jaki kawałek wybrać, tak żeby było w nim jak najwięcej orzechów. Kawałek ten może być wybrany z dowolnego miejsca w czekoladzie, nawet ze środka tabliczki. Pomóż Zosi.
Napisz procedurę \(\mathtt{orzechy} : \mathtt{int} \to \mathtt{int~array~array} \to \mathtt{int}\), która mając dane: liczbę \(k\) (\(k > 0\)) oraz prostokątną tablicę nieujemnych liczb całkowitych, określającą ile orzechów znajduje się w poszczególnych kosteczkach tabliczki czekolady, wyznaczy maksymalną liczbę orzechów w kawałku czekolady, który może zjeść Zosia.
Możesz założyć, że tabliczka czekolady jest na tyle duża, że zawiera przynajmniej jeden prostokątny kawałek czekolady złożony z dokładnie \(k\) kosteczek.
Na przykład, dla \(k = 6\) oraz tablicy:
\[
\begin{array}{|c|c|c|c|c|c|}
\hline
0 & 0 & 4 & 1 & 2 & 0 \\\hline
3 & 3 & 8 & 11 & 3 & 2 \\\hline
1 & 3 & 9 & 8 & 1 & 2 \\\hline
2 & 1 & 1 & 2 & 0 & 12 \\\hline
\end{array}
\]
poprawnym wynikiem jest 42.
-
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\).
- [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.
- [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.
- [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ć?
- [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ń.
- [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.