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

14400. Palindrom wielokrotny [AL_05_04]

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

Skrócony opis problemu:

Dla $t$ danych stringów znajdź dla każdego stringa $s_i$ jego krotność palindromiczną $k_i$, a następnie znajdź i wypisz medianę zbioru $k_i$.

Krotność palindromiczna jest zdefiniowana następująco:

• jeśli wyraz nie jest palindromem, to jego krotność wynosi 0 - jest palindromem 0-krotnym
• jeśli wyraz ma jedną literę, to jest palindromem 1-krotnym
• jeśli wyraz $s$ jest palindromem $k$-krotnym, to wyrazy $s + s$ (+ oznacza konkatenację, czyli sklejanie stringów) oraz $s + c + s$ (gdzie $c$ to jakiś znak) są palindromamy $n+1$-krotnymi

Np. "abc" ma krotność 0, "kajak" ma krotność 1, "oko" ma krotność 2, "oooo" ma krotność 3, a "aabaacaabaa" ma krotność 4.

14783. Dobra i zła energia [AL_06_05]

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

Skrócony opis problemu:

Dla macierzy $n$x$n$ należy znaleźć największą sumę dowolnej podmacierzy.

Uwaga: Warto zapoznać się najpierw z wersją jednowymiarową opisaną tutaj. Będę na niej bazował. Problem dla wersji jednowymiarowej to znalezienie podłańcucha o największej sumie.

1299. Stefan [FZI_STEF]

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

Skrócony opis problemu:
Dla podanego ciągu $n$ liczb należy znaleźć podłańcuch o maksymalnej sumie.

8981. Zamiana miejsc [WYMIANA]

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

Skrócony opis problemu:

Zamień wartości 2 zmiennych $x$ i $y$ bez korzystania z dodatkowych zmiennych.

15290. Wakacje [AL_08_06]

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

Skrócony opis problemu:

Dla danych liczb $x$, $n$ ($x \le 10^4, n \le 100$) oraz $n$-elementowej tablicy wybrać z tablicy takie liczby, aby ich suma była $\ge x$ i przy tym była minimalna. Jeśli jest wiele takich podzbiorów danej tablicy to znaleźć najmniej liczny.

15533. Klasyka 1 [AL_09_08]

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

Skrócony opis problemu:

Dla danego tekstu $s$ o długości $n$ i wzorca $p$ o długości $m$ ($m \le n$) należy znaleźć ilość wystąpień $p$ w $s$. Zarówno $s$ jak i $p$ składają się z małych liter alfabetu łacińskiego, lecz w $p$ może pojawić się jeden znak '?', który będzie oznaczał dowolny znak.

505. Cwany Lutek [CWANY_LU]

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

Skrócony opis problemu:

Sprawdź czy dla danych $n$ i $k$ ($n, k \in \left<0;10^9\right>$) $\binom{n}{k}$ jest liczbą parzystą czy nieparzystą.

15510. Gra [AL_09_07]

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

Skrócony opis problemu:

Dana jest moneta, na której wypada orzeł z prawdopodobieństwem $\frac{2}{3}$, a reszka z $\frac{1}{3}$. Czy prawdopodobieństwo $P(A)$, że w $n$ rzutach wypadło $k$ reszek jest większe, mniejsze czy równe prawdopodobieństwu $P(B)$ przy dodatkowej wiedzy, że w pierwszym rzucie wypadła reszka?

15281. Odległość [AL_08_05]

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

Skrócony opis problemu:

Dla dwóch permutacji $a$ i $b$ ciągu o długości $n$ oblicz odległość między nimi. Odległością nazywamy ilość przekształceń z jednej permutacji w drugą.

Np. odległością między permutacjami 1987 i 7891 (dla ciągu ${1, 7, 8, 9}$ o długości $n=4$) jest 4, gdyż kolejne przekształcenia to:

0 1987

1 7189

2 7198

3 7819

4 7891

Pierwsza permutacja ma numer 0, gdyż nie musieliśmy wykonywać żadnego przekształcenia. Przekształcenie to zatem zamiana jednej permutacji w następną leksykograficznie.

Cyfry w ciągu nie powtarzają się.

1041. Króliczki Jasia [KRO]

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

Skrócony opis problemu:

Mając dane 2 początkowe wyrazy ciągu Fibonacciego $a$ i $b$ oraz liczbę $n$ mamy wypisać ostatnią cyfrę $n$-tego wyrazu tego ciągu.

2217. Statystyka pozycyjna [KC022]

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

Skrócony opis problemu:

Dla danej liczby $k$ należy wypisać $k$-tą statystykę pozycyjną. Innymi słowy należy wypisać $k$-tą największą liczbę z podanego zbioru (nie multizbioru - usuwamy duplikaty), a jeśli nie istnieje, to wypisać znak '-'.

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.

497. Trójkąty Jednobarwne [TROJEDNO]

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

Skrócony opis problemu:

Mając dane $n$ będące stopniem grafu pełnego oraz $m$ czerwonych krawędzi tego grafu (pozostałe $\frac{n(n-1)}{2}-m$ krawędzi jest czarna) oblicz ilość jednobarwnych trójkątów w tym grafie. Jednobarwny trójkąt, to taka trójka wierzchołków, że wszystkie 3 krawędzie między nimi są jednego koloru.

Np. dla $n=6, m=9$ i tych czerwonych krawędzi: 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, 1-4, 2-5, 3-6 wynik to 2. Graf ten bowiem wygląda następująco:

Jak widzimy, są 2 trójkąty jednobarwne: 1-3-5 oraz 2-4-6.

14787. Termin drugi [AL_06_09]

Zadanie:

http://pl.spoj.com/problems/AL_06_09/

Skrócony opis problemu:

Problem przedstawia szyfrowanie z kluczem publicznym.

Na początek bierzemy pewien ciąg (superrosnący) a_k, którego każdy wyraz jest większy od sumy wyrazów poprzednich. Następnie ustalamy dwie względnie pierwsze liczby n i m, takie, że n jest względnie pierwsze ze wszystkimi elementami ciągu a_k oraz m jest większe od  sumy wszystkich wyrazów ciągu a_k. Każdy wyraz ciągu szyfrujemy według zasady:

b_i =  a_i $\cdot$ n mod m, dla 1 $\leq$ i $\leq$ k 

W ten sposób otrzymaliśmy ciąg b_k.

Wiadomość, którą chcemy zaszyfrować dzielimy na segmenty binarne o długości k a następnie szyfrujemy w taki sposób, że sumujemy tylko te elementy ciągu b_k., które odpowiadają wartości 1 w segmencie binarnym.

Np. jeśli ciąg b_k. ma postać: {1, 3, 5, 10}, dla n = 4, a wiadomość ma trzy segmenty o długości 4:

1100 0110 1111

to szyfrogram będzie wyglądał następująco:

I segment: 1 + 3 = 4

II segment: 3 + 5 = 8

III segment: 1 + 3 + 5 + 10 = 19.

Ciąg {4, 8, 19} jest szyfrogramem.

Na podstawie danych: n, m, k, ciągu a_k oraz szyfrogramu należy podać oryginalną wiadomość w postaci binarnej.

15280. Szpieg u bram wioski [AL_08_04]

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

Skrócony opis problemu:

Dla danego wyrazu $str$ o długości $n$ znajdź długość najdłuższego (niekoniecznie spójnego) palindromu, który zawiera.

Np. dla wyrazu "algoliga" odpowiedź to 5. Najdłuższe palindromy to bowiem: "algla", "alola", "agoga", "aglga" i "agiga" (wszystkie mają długość 5).

15203. Plansza [PLA]

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

Skrócony opis problemu:

Dla danych $n$, $m$, $k$ ($n, m, k \le 8000$), należy wypisać liczbę możliwych przejść z lewego dolnego rogu macierzy o wymiarach $n$x$m$ do prawego górnego rogu, mogąc wykonać kroki o długości od 1 do $k$. Krok o długości 1 definiujemy przez poruszenie się w prawo, do góry lub w prawo do góry. Ruch o długości 2, to na przykład przesunięcie się z pola (0;0) do pola (2;2). Wynik należy podać modulo $10^9+103$.

12219. Jasio kryptolog [AL_01_04]

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

Skrócony opis problemu:

Zadanie dotyczy szyfrowania RSA, więc na pewno przed jego rozwiązywaniem należy zapoznać się z tym systemem na przykład pod tym linkiem: RSA na wikipedii.

Na wejściu dostajemy dwie różne liczby pierwsze $p,q<4\cdot 10^9$ oraz liczbę $e<\phi(pq), \ \gcd(e,\phi(pq))=1$, tak że para $(pq,e)$ stanowi klucz publiczny szyfrowania. Oznaczmy $n=pq$. Chcemy się dowiedzieć ile komunikatów ze zbioru $\left\{0,..,n-1\right\}$ po zaszyfrowaniu taką metodą nie zmienia swojej postaci. Inaczej mówiąc pytamy o: $\left|\left\{M\in\left\{0,..,n-1\right\}: M^e \equiv M \pmod{n}\right\}\right|$ - liczbę punktów stałych szyfrowania RSA.

15509. Wycieczka 2 [AL_09_06]

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

Skrócony opis problemu:

Otrzymujesz na wejściu macierz sąsiedztwa $M$ o rozmiarze $n$ oraz macierz $N$, w której w $i$-tym wierszu i $j$-tej kolumnie powinna być ilość dróg z wierzchołka $i$ do wierzchołka $j$ o długości 2 (a więc z dokładnie jednym pośrednikiem; 2 oznacza ilość krawędzi, a nie wierzchołków). Twoim zadaniem jest zweryfikowanie czy faktycznie dla każdej pary wierzchołków $(i;j)$ na wejściu podano prawidłową liczbę $N_{i,j}$ dróg o długości 2 między tymi wierzchołkami. Jeśli w macierzy $N$ wszystkie liczby się zgadzają wypisz TAK. W przeciwnym wypadku wypisz NIE.

Np. dla macierzy sąsiedztwa:

0 1

1 0

Od wierzchołka 1 można przejść do wierzchołka 1 na 1 sposób (przez wierzchołek 2), od 2 do 2 też na 1 (przez wierzchołek 1), ale już od 1 do 2 i od 2 do 1 nie można (więc na 0 sposobów). Macierz $N$ powinna zatem wyglądać tak:

1 0

0 1

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.

8736. Arka Noego [NOE]

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

Skrócony opis zadania:

Mając $n$ liczb z przedziału $\left<1;10^9\right>$ znajdź liczbę, która nie ma pary (wszystkie pozostałe mają).

Np. dla liczb: 1 2 3 2 1 wynik to 3, gdyż 1 i 2 mają pary.

12983. Najdłuższy spójny podciąg ciągu binarnego [AL_03_02]

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

Skrócony opis problemu:

Dla podanego ciągu binarnego (składającego się tylko z 0 i 1) o długości $n$, znaleźć długość najdłuższego spójnego podciągu zawierającego maksymalnie $k$ jedynek.

1054. Róże przed domami [ROZ]

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

Skrócony opis problemu:

Mamy $n$ trójek liczb naturalnych i naszym zadaniem jest wybrać taką drogę od pierwszej do ostatniej trójki, żeby suma liczb, przez które przejdziemy była najmniejsza, ale przy warunku, że jeśli weźmiemy w którymś kroku 2-gą liczbę, to w następnym możemy wziąć tylko 1-szą lub 3-cią.

Np. dla $n=5$ i trójek:

8 9 9

0 9 9

3 9 4

8 4 1

8 4 1

Najkrótsza droga to 9-0-4-4-1. Jeśli jest więcej dróg, to nieważne, którą wybierzemy, bo wypisać musimy tylko sumę. Wynik w tym przypadku to zatem 18.

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.

9538. Kot pucybut [KOTYYYYY]

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

Skrócony opis problemu:

Stoją sobie 2 koty na prostej podzielonej na jednostki. Każdy z nich może się poruszyć o 1 lub 2 pola w kierunku przeciwnika. Ruchy wykonują naprzemiennie. Wygrywa kot, który uniemożliwi przeciwnikowi ruch - nie można przesunąć się na zajęte pole oraz przeskoczyć przeciwnika. Który kot wygra, zakładając, że oba grają optymalnie?

628. Półki [SHELVES]

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

Skrócony opis problemu:

Mając półki ustawione ukośnie w $n$ ($n \le 1000$) kolumnach oraz $k$ ($k \le 250000$) piłek, które są kolejno spuszczane w różnych kolumnach z górnych półek określ gdzie spadnie ostatnia piłka, jeśli po każdym stoczeniu się piłki po półce odwraca się jej ustawienie (jeśli nie jest ona półką skrajną). A więc półki \ zamieniają się na / i odwrotnie.

Przykładowo, jeśli mamy jedną piłkę i taki zestaw półek:

o    
\ \ /
 / / 
\ \ /

To po sturlaniu się piłki po wszystkich 3 półkach, ich rozkład będzie wyglądał następująco:

\ \ /
 \ / 
\ \ /
o  

Jak widać, półki po bokach nie zmieniają nachylenia, gdyż wtedy piłka wypadłaby poza planszę. Zmianie uległa więc tylko nachylenie czerwonej półki.

W zadaniu półki \ są podane jako 1, a / jako -1.