629. Skąpiec [MISER]

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

Skrócony opis problemu:

Dla danego zbioru $n$ punktów w przestrzeni 2-wymiarowej należy wyznaczyć dowolne 2 punkty, takie że okrąg utworzony na nich oraz na pierwszym punkcie z wejścia (nazwijmy go $A$) nie zawiera w sobie żadnego innego punktu (mogą jednak się znaleźć punkty na samym okręgu). Żadne 3 punkty nie są współliniowe.

4622. PTwPZ Paleta [PTWPZ096]

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

Skrócony opis problemu:

Mamy listę $n$ kolorów modelu RGB, czyli w postaci trójki liczb z przedziału $\left<0; 255\right>$. Mamy następnie $m$ zapytań będących również pojedynczymi kolorami RGB. Dla każdego koloru z zapytania należy znaleźć najbliższy mu kolor z listy, którą dostaliśmy na początku. Odległość jest w metryce euklidesowej (czyli $odl(col1, col2) = \sqrt{\left(col1.r-col2.r\right)^2 + \left(col1.g-col2.g\right)^2 +\left(col1.b-col2.b\right)^2}$). Jeśli 2 punkty będą w tej samej odległości, to należy wybrać ten z większą składową czerwoną. Jeśli i one będą równe - z większą składową zieloną i ew. z większą składową niebieską. Kolory rozłożone są równomiernie na obszarze, który zajmują (a nie np. tylko na zewnętrznych ścianach lub prawie tylko w centrum).

573. Marsze na orientację [PZPI1]

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

Skrócony opis problemu:

Mamy $n$ punktów numerowanych od 1 do $n$ oraz $k$ ($k < n$) zapytań. Zapytanie składa się z dwóch liczb: $a$ i $b$. Dla każdego zapytania należy podać dowolną ścieżkę z punktu $a$ do punktu $b$ (przechodząc przez inne punktu po drodze lub nie), jednak żadne dwie trasy (będące odpowiedzią na zapytania) nie mogą mieć wspólnego fragmentu (bezpośredniego połączenia między tą samą parą punktów). Czyli po prostu musimy wypisywać dowolne ścieżki, ale bez wspólnych krawędzi. Jeżeli dla danego testu nie da się utworzyć ścieżek, które by spełniały kryteria z zadania, to należy wypisać NIE.

1144. Autobus [MWPZ06C]

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

Skrócony opis problemu:

Do $n$-osobowego autobusu wsiada $m$ osób. Jest 1 rząd miejsc siedzących. Pierwsza osoba siada na miejscu $x$. Kolejne osoby siadają wg następujących zasad:

• kolejna osoba wybiera miejsce, którego odległość do najbliższego zajętego miejsca jest jak największa
• jeżeli miejsc, na których może usiąść naukowiec (zgodnie z poprzednim punktem) jest więcej to wybiera on takie, które jest najbliżej wejścia (tj. z najmniejszym numerkiem)
• naukowcy nie zwracają uwagi na fakt istnienia kierowcy w autobusie

Dla $y$ wybranych osób należy podać ich miejsca (numerowane od 1 do $n$).

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

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.

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.

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

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.

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.