10348. Taksówka na Manhattanie 4 [TAXIMAN4]

Zadanie:
https://pl.spoj.com/problems/TAXIMAN4

Skrócony opis problemu:

Dla danych $n$ ($n \le 10^5$) punktów z przestrzeni $d$-wymiarowej (mających $d < 17$ współrzędnych) wypisać odległość w metryce Manhattan między dwoma najdalszymi punktami.

8994. Taksówka na Manhattanie [TAXIMAN]

Zadanie:
https://pl.spoj.com/problems/TAXIMAN

Skrócony opis problemu:

Mając dane $n$ punktów, znajdź odległość między dwoma najbardziej oddalonymi od siebie punktami (w metryce Manhattan - np. odległość między $(1;1)$ a $(2;2)$ to 2, bo trzeba iść 1 w górę i 1 w prawo).

15157. Neptun [AL_07_08]

Zadanie:
https://pl.spoj.com/problems/AL_07_08

Skrócony opis problemu:

Mamy dane graf nieskierowany składający się z $v$ wierzchołków (ang. vertex), które numerujemy od 0 i $e$ krawędzi (and. edges). Następnie mamy podane $n$ i $n$ wierzchołków reprezentujących stolice państw, opisanych ich numerem oraz wartością $m$. Każda stolica podbija wszystkie sąsiednie i niepodbite jeszcze tereny (wierzchołki) po czasie $m$. Po czasie $2m$ każdy z nowopodbitych terenów podbija z kolei wszystkich swoich [niepoditych] sąsiadów, i tak do zużycia (podbicia) wszystkich wierzchołków. Następnie podana jest liczba $q$ (ang. query) oznaczająca ilość zapytań. Każde zapytanie składa się z dwóch liczb: $a$, $b$ i należy dla niego wypisać numer jednej ze $n$ stolic (numer, a nie wartość tak więc jeśli trzecią stolicą jest 5, to jej numerem jest 3), która okupuje w momencie $b$ teren (wierzchołek) $a$ Jeśli w momencie $b$ teren jest niezajęty, to należy wypisać "-". Jeśli w danej jednostce czasu jakiś teren chcą podbić dwie stolice to podbija go ta z mniejszym numerem.

15159. Balony [AL_07_10]

Zadanie:
https://pl.spoj.com/problems/AL_07_10

Skrócony opis problemu:

Dane jest $n$ sal, $m$ pomocników oraz ilość uczestników konkursu $x_i$ w każdej z $n$ sal. W każdej sali musi być przynajmniej 1 pomocnik. Oblicz maksymalną ilość uczestników przypadającą na jednego pomocnika zakładając optymalne rozmieszczenie pomocników. Innymi słowy musisz tak poprzydzielać pomocników do sal, aby zminimalizować maksymalną ilość uczestników na pomocnika.

Np. dla $n=3, m=6$ i $x = [10, 30, 90]$ wynikiem jest 30, bo do pierwszej sali przydzielamy 1 pomocnika i: albo do drugiej 1, a do trzeciej 4 - wtedy w drugiej 1 pomocnik musi radzić sobie z 30 uczestnikami, albo do drugiej 2, a do trzeciej 3 - wtedy w trzeciej sali jest 3 pomocników na 90 uczestników (czyli każdy pomocnik ma przydzielonych 30 uczestników).