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).

15153. Do odpowiedzi! [AL_07_04]

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

Skrócony opis problemu:

Mając tablicę o rozmiarze $n$, przechodzimy ją zmieniając pozycję o kolejne liczby pierwsze i oznaczając komórki, na których stanęliśmy jako "zużyte". Komórki te pomijamy przy poruszaniu się. Gdy dojdziemy do końca to przeskakujemy na początek tablicy. Na koniec pozostaje tylko jedna niezużyta komórka i to jej numer mamy wypisać (zaczynając numerację od 1).

Np. dla $n=4$:

$$1234 \rightarrow 1X34 \rightarrow XX34 \rightarrow XXX4$$

W pierwszym kroku skreślamy drugą liczbę. W drugim zmieniamy pozycję o 3 - 3, 4, 1 i skreślamy to 1. W ostatnim zmieniamy pozycję o 5: 3, 4, 3, 4, 3 - skreślamy zatem 3. Wynik to 4.

11123. Fibonacci [MWP4_2A]

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

Skrócony opis problemu:

Mając daną liczbę $x$ należy znaleźć 2 pierwsze liczby ciągu Fibonacciego, który kończy się właśnie liczbą $x$, ale jest możliwie najdłuższy. Jeśli jest wiele ciągów o tej samej długości, to należy wybrać ten o najmniejszym pierwszym elemencie.

5139. Nieosiągalna liczba [WZP09_2C]

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

Skrócony opis problemu:

Mając dane $n$ oraz $n$ liczb posortowanych rosnąco i mamy wypisać najmniejszą liczbę, której nie da się otrzymać poprzez zsumowanie dowolnej ilości danych liczb.

11059. Prefiks równoważący sufiks [MWP4_1E]

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

Skrócony opis problemu:

Dla danego ciągu liczb o długości $n$, znajdź najmniejszy indeks, dla którego suma liczb za nim jest równa sumie liczb od początku do niego włącznie. Jeśli taki indeks nie istnieje - wypisz 0.

Na przykład dla $n=5$ i ciągu 4,2,3,2,1 wynik to 2 (liczymy indeksy od 1), bo dla drugiej liczby mamy: 4+2=3+2+1.

15154. Cięcia [AL_07_05]

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

Skrócony opis problemu:

Mając dany prostokąt w układzie współrzędnym, a także proste pionowe i poziome przecinające ten prostokąt, wypisz pole największego kawałka tego prostokąta przeciętego przez te proste oraz ilość tych największych kawałków. Jest $n$ prostych - pionowe opisane są liczbami naturalnymi, a poziome całkowitymi ujemnymi.