-
Dany jest graf nieskierowany, którego wierzchołki są ponumerowane od 0 do \(n-1\).
Napisz procedurę \(\mathtt{path}: \mathtt{graph} \to \mathtt{int}\), która wyznacza długość (liczoną liczbą krawędzi) najdłuższej ścieżki w tym grafie, na której numery wierzchołków tworzą ciąg rosnący.
- [II OI, zadanie Klub Prawoskrętnych Kierowców, PCh]
Mamy dany układ ulic, leżących na prostokątnej siatce \(m \times n\).
Ulice są jedno- lub dwukierunkowe.
Przyjmujemy, że cztery strony świata są reprezentowane za pomocą liczb całkowitych od 0 do 3:
let north = 0 and east = 1 and south = 2 and west = 3;;
Układ ulic jest dany w formie trójwymiarowej tablicy wartości logicznych ulice: \(\mathtt{ulice}.(i).(j).(k)\)
określa, czy z punktu o współrzednych \((i,j)\) można przejechać w kierunku k jedną jednostkę odległości.
Można założyć, że tablica ta uniemożliwia wyjechanie poza obszar \(\{0,\dots,m-1\} \times \{0,\dots,n-1\}\).
Członkowie Klubu Prawoskrętnych Kierowców na skrzyżowaniach jeżdżą prosto lub skręcają w prawo.
Sprawdź, czy z punktu \((0,0)\) prawoskrętny kierowca może dojechać do punktu \((m-1, n-1)\).
-
Jaka jest minimalna liczba monet potrzebna do wydania \(n\)zł reszty, przyjmując, że monety mogą być przekazywane w obie strony.
(Na przykład, żeby otrzymać 9 zł mogę dać 1 zł i otrzymać 10 zł, razem 2).
W obrocie są dostępne monety o zadanych (w postaci tablicy) nominałach.
-
Dana jest prostokątna mapa wysokości górzystego terenu, w postaci prostokątnej tablicy dodatnich liczb całkowitych, o wymiarach\(N \times M\).
Chcemy przejść z pola o współrzędnych\((0,0)\) na pole o współrzędnych\((N-1, M-1)\), ale nie chcemy wspinać się zbyt wysoko.
(Możemy się przesuwać w kierunkach N, W, S, E.)
Napisz procedurę\(\mathtt{wysokosc} : \mathtt{int~array~array} \to \mathtt{int}\), która dla danej mapy terenu określi
minimalną największą wysokość, na którą musimy wejść w trakcie podróży.
-
W parku jest prostokątna sadzawka pokryta lodem. Jaś bawi się na lodzie. Niestety przyszła odwilż i lód zaczął pękać.
Masz daną prostokątną tablicę zawierającą dodatnie liczby całkowite. Jest to mapa sadzawki, a liczby reprezentują moment, w którym lód w danym miejscu pęka.
Napisz procedurę \(\mathtt{sadzawka}: \mathtt{int~array~array} \to (\mathtt{int} * \mathtt{int}) \to \mathtt{int}\), która mając daną taką tablicę oraz współrzędne miejsca, w którym bawi się Jaś, wyznaczy moment, w którym Jaś straci możliwość wyjścia na brzeg (bo albo zostanie odcięty od brzegu spękanym lodem, albo wpadnie do wody).
Możesz założyć, że:
- Jaś może poruszać się po polach sąsiadujących ze sobą bokami,
- Jaś porusza się nieporównanie szybciej, niż postępuje pękanie lodu,
- liczby w danej tablicy są z zakresu od 1 do liczba elementów w tablicy.
-
Dana jest prostokątna mapa \(n \times m\) przedstawiająca archipelag na oceanie, reprezentowana jako
bool array array.
Elementy tablicy równe true reprezentują ląd, a false wodę.
Na zewnątrz mapy znajduje się ocean.
Wyspy na oceanie są wyspami rzędu 1.
Na wyspach rzędu 1 mogą znajdować się jeziora rzędu 1, na nich mogą znajdować się wyspy rzędu 2 itd.
Ogólnie:
-
ocean ma rząd 0,
-
wyspa na jeziorze (lub oceanie) rzędu \(k\), ma rząd \(k+1\),
-
jezioro na wyspie rzędu \(k\) ma rząd \(k\).
Pola wody przylegające do siebie bokami lub rogami należą do tego samego jeziora (lub oceanu).
Pola lądu przylegające do siebie bokami należą do tej samej wyspy.
Napisz procedurę \(\mathtt{wyspa}: \mathtt{bool\ array\ array} \to \mathtt{int}\), która dla danej mapy zwróci maksymalny rząd wyspy na mapie.
Jeżeli na oceanie nie ma żadnej wyspy, to procedura powinna zwrócić 0.
Przykład: 69.793N, 108.241W.
-
[J.Paw.]
Dany jest nieskierowany graf \(g\) oraz trzy wierchołki w tym grafie: \(u\), \(v\) i \(w\).
Napisz procedurę \(\mathtt{polaczenie}: \mathtt{graph} \to \mathtt{int} \to \mathtt{int} \to \mathtt{int} \to \mathtt{int}\), która mając dane \(g\), \(u\), \(v\) i \(w\) wyznaczy minimalną liczbę krawędzi w grafie, jakie są konieczne, żeby wierzchołki \(u\), \(v\) i \(w\) pozostały połączone.
Jeżeli nie jest to możliwe, poprawnym wynikiem jest \(-1\).
- [XIV OI, zadanie Biura]
Firma ma n pracowników.
Każdy pracownik ma telefon komórkowy, a w nim telefony pewnej grupy innych pracowników.
Przy tym, jeżeli pracownik A ma telefon pracownika B, to pracownik B ma numer pracownika A.
Firma chce podzielić pracowników na grupy, w taki sposób żeby:
- każdych dwóch pracowników albo było w tej samej grupie, albo miało nawzajem swoje numery telefonów,
- liczba grup była maksymalna.
Wyznacz podział pracowników na grupy.
- [II OI, zadannie Palindromy]
Podziel dane słowo (listę znaków) na minimalną liczbę palindromów parzystej długości.
-
Dany jest acykliczny graf skierowany (DAG).
Jego wierzchołki są ponumerowane od 0 do n, a krawędzie są dane w postaci tablicy sąsiedztwa
(kwadratowej tablicy e wartości logicznych; w grafie mamy krawędź \(u\!\!\to\!\!v\) wtw., gdy \(\mathtt{e}.(u).(v)\)).
Powiemy, że wierzchołek u dominuje wierzchołek v, jeżeli dla każdego wierzchołka w,
z którego można dojść do v, z u można dojść do w.
Napisz procedurę zdominowani : bool array array -> int, która na podstawie tablicy opisującej graf
obliczy liczbę wierzchołków, dla których istnieją wierzchołki je dominujące.
- [XIV OI, zadanie Powódź]
Dana jest mapa topograficzna miasta położonego w kotlinie, w postaci prostokątnej tablicy typu (int * bool) array array.
Liczby określają wysokość kwadratów jednostkowych, a wartości logiczne określają, czy dany kwadrat należy do terenu miasta.
Przyjmujemy, że teren poza mapą jest położony wyżej niż jakikolwiek kwadrat na mapie.
Miasto zostało całkowicie zalane.
Żeby je osuszyć należy w kotlinie rozmieścić pewną liczbę pomp.
Każda z pomp wypompowuję wodę aż do osuszenia kwadratu jednostkowego, na którym się znajduje.
Osuszenie dowolnego kwadratu pociąga za sobą obniżenie poziomu wody lub osuszenie kwadratów jednostkowych, z
których woda jest w stanie spłynąć do kwadratu, na którym znajduje się pompa.
Woda może przepływać między kwadratami, które stykają się bokami.
Wyznacz minimalną liczbę pomp koniecznych do osuszenia miasta.
Teren nie należący do miasta nie musi być osuszony.
Miasto nie musi tworzyć spójnego obszaru.