17206. Gra w mnożenie [AL_12_03]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_03
http://pl.spoj.com/problems/AL_12_03

Skrócony opis problemu:

Zaczynamy od $p=1$. Gracze A i B mnożą na przemian $p$ przez $x \in \left\lbrace 2,3,4,5,6,7,8,9\right\rbrace$ aż $p \ge n$. Gracz, który ostatni przemnoży $p$ wygrywa. Zaczyna gracz A. Naszym zadaniem jest określić który gracz wygra, zakładając, że obaj grają optymalnie.

17204. Winda [AL_12_01]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_01
http://pl.spoj.com/problems/AL_12_01

Skrócony opis zadania:

Jest nam dany string (o długości $m$) opisujący historię operacji windy. Litera D oznacza, że winda pojechała jedno piętro w dół, a U oznacza, że pojechała do góry. Naszym zadaniem jest stwierdzić czy dana historia jest poprawna, czyli winda nie zjechała poniżej parteru (o numerze 1) lub nie wjechała powyżej najwyższego piętra (o numerze $n$).

17207. Konkatenacja liczb [AL_12_04]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_04
http://pl.spoj.com/ALGOLIGA/problems/AL_12_04

Skrócony opis problemu:
Dla podanych n liczb znaleźć taką ich konkatenację, by jej wartość była największa.

17211. Bajtomir na giełdzie [AL_12_08]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_08
http://pl.spoj.com/problems/AL_12_08

Skrócony opis problemu:

Dla danego ciągu składającego się z $n$ liczb naturalnych znaleźć najdłuższy podciąg alternujący (ang. longest alternating subsequence). Jest to taki ciąg, dla którego kolejne wyrazy są na przemian rosnące i malejące. Np. 2,3,1 lub 5,1,99,42.

17215. Głuchy telefon epicykloidorów [AL_12_12]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_12
http://pl.spoj.com/problems/AL_12_12

Skrócony opis problemu:

Mamy sobie koło, na którym jest $n$ równo-oddalonych od siebie punktów. Z każdego punktu może wyskoczyć epicykloidor i poruszając się o jakąś odległość $l_i$ może przemieścić się do dowolnego innego punktu. Mamy również daną listę wszystkich możliwych $l_i$ - jest ich $m$. Głuchy telefon polega na tym, że z punktu $a$ wyskakuje epicykloidor o jakimś $l_i$ i wskakuje do punktu oddalonego o $l_i$. Z tego punktu wyskakuje kolejny epicykloidor (możliwe, że o innym $l_j$) i wskakuje do punktu oddalonego o $l_j$. I tak aż osiągnie się punkt $b$. Dla każdego z $q$ zapytań należy wypisać liczbę możliwych ścieżek (nie dróg!) z punktu $a$ do punktu $b$ o długości $x$ skoków. (Będąc w punkcie $b$ epicykloidor może potraktować go jako punkt pośredni, a nie końcowy i wykonać jeszcze kilka skoków przed zakończeniem rundy w punkcie $b$). Punkty są mają wartości rosnące zgodnie z kierunkiem ruchu wskazówek zegara. Wynik należy podać modulo 1010101.

17214. Festyn w Bajtlandii [AL_12_11]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_11
http://pl.spoj.com/problems/AL_12_11

Skrócony opis problemu:
Jest $n$ wież o danych wysokościach oraz $q$ zapytań.
TODO

17208. Bajtek w przedszkolu [AL_12_05]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_05
http://pl.spoj.com/ALGOLIGA/problems/AL_12_05

Skrócony opis problemu:

Dla ciągu $n$ liter 'C' i $n$ liter 'K' wypisać najmniejszą sumę kosztów połączeń między literami 'C' z literami 'K', gdzie koszt połączenia to odległość między tymi literami. Np. koszt połączenia dla CK to 1, dla CXK to 2, dla CXXK to 3, itd. Dla CKCK wynik to 2, gdyż łączymy pierwsze C z pierwszym K i ostatnie C z ostatnim K.

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.

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.

14785. Zerówka [AL_06_07]

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

Skrócony opis problemu:

Dla podanej funkcji kwadratowej $f(x) = ax^2+bx+c$ oraz przedziału argumentów $\left<A;B\right>$ podaj ile jest wartości całkowitych funkcji w tym przedziale.

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.

14403. Linia brzegowa [AL_05_07]

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

Skrócony opis problemu:

Mając macierz $n$ na $m$ będącą mapą, składającą się z lądu: 'X' i wody: '.' oblicz długość linii brzegowej wszystkich lądów i wysp. Brzegi jezior i wysp na tych jeziorach nie mają być brane pod uwagę.

Np. dla takiej macierzy 5x6:

.XXXX.
.X.XX.
XXX...
....X.
......

Wynik to 20, bo tak wygląda owa linia brzegowa (niektóre komórki liczymy więcej niż 1 raz):

..1111.
.1XXXX1
.2X.XX1
1XXX22.
.1111X1
.....1.

1109. Aproksymacja Średniokwadratowa Dyskretna [MN06_7]

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

Skrócony opis problemu:

Dla $n$ punktów reprezentowanych przez argument $x_i$, wartość $f(x_i)$ oraz wagę $w(x_i)$ oraz $m$ funkcji bazowych wyznacz funkcję aproksymującą $F(x)$. Następnie oblicz wartości tej funkcji dla danych $n'$ argumentów $x_i'$.

11833. Bajtocki Inspektorat Ochrony Środowiska 3 [BAJTIOS3]

Zadanie:
http://pl.spoj.com/problems/BAJTIOS3

Skrócony opis problemu:

Otrzymujemy $n \le 100000$ liczb. Każda z nich ($x_i$) ma przypisany indeks $i$. Następnie otrzymujemy $m \le 10000$ trójek liczb: $a$, $b$, $y$. Zadanie polega na znalezieniu dla każdego zapytania (j-tego) ilości takich $x_i$, że $i \in \left<a;b\right>$ oraz $x_i > y_j$.

4651. PTwPZ Zamek [PTWPZ078]

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

Skrócony opis problemu:

Mamy liczby $n$ i $m$ ($n,m \le 10000$) oznaczające odpowiednio ilość wierzchołków i krawędzi w digrafie oraz liczbę $t$ ($t<21$) i $t$ liczb oznaczających wierzchołki specjalne. Mamy wypisać z ilu wierzchołków (niekoniecznie zwykłych) da się dojść do wszystkich wierzchołków specjalnych.

13696. Drzwi Adriana [DALGO]

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

Skrócony opis problemu:

Jest $n$ testów. Każdy z nich składa się z $3$ liczb: $p$, $q$ i $m$. Mając liczby $p$ i $q$ należy znaleźć takie liczby $x$ i $y$, że $x \cdot p + y \cdot q=NWD(p,q)$, ale tak, aby $x \ge 0$ oraz by $x$ było minimalne.

Następnie należy nadpełnić przedział $\left<\min(x,y);\max(x,y)\right>$ liczbą $m$ (czyli do każdego elementu z przedziału dodać liczbę $m$). Po wykonaniu wszystkich testów należy wypisać cały przedział.

13536. Dostawca PRK [AL_04_01]

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

Skrócony opis problemu:

Mamy $n \le 10^5$ punktów o współrzędnych z przedziału $\left<-10^9;10^9\right>$. Chcemy znaleźć sumę odległości między każdymi dwoma punktami.