Runda 15 [Hard] - Wieża strażnicza

14.03.2011 - Damian Rusak

Zadanie tygodnia

runda 15; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 64MB

Wieża strażnicza

Zaiste nadeszły ciężkie czasy dla naszego królestwa. Wrogowie coraz tłumniej i bezczelniej naruszają nasze granice, kataklizmy i klęski żywiołone nawiedzają nasze ziemie a nasi poddani coraz częściej uczą się czytać i pisać. Przynajmniej to pierwsze niebezpieczeństwo można odsunąć w czasie - oto wzdłuż granicy nasi przodkowie zbudowali onegdaj długi ciąg wież. Jedna z nich jest siedzibą nadwornego maga, reszta pozostała niezagospodarowana.

Planujemy wykorzystać tę sytuację i wybrać pewien podciąg tych wież oraz umieścić w nich zbrojne drużyny, gotowe bronić granicy przed najazdami wrażych sił. Nasz nadworny mag jest niezbędny w tych planach - jego wieża musi znaleźć się w wybranym podciągu. Ponadto dla celów militarnych wysokości kolejnych wież (licząc od tej najbardziej na lewo do tej najbardziej na prawo) muszą tworzyć ciąg arytmetyczny. Oczywiście, chcemy aby wybrany podciąg był jak najdłuższy.

Przypominamy, że podciąg nie musi być spójny! To znaczy z ciągu $a_{1}$ , $a_{2}$ , ..., $a_{n}$ można wybrać dowolny ciąg $a_{i_{1}}$ , $a_{i_{2}}$ , ..., $a_{i_{m}}$ jeśli $i_{1}$ < $i_{2}$ < ... < $i_{m}$ . Podciąg taki jest arytmetyczny w naszym rozumieniu, jeśli $a_{i_{1}} - a_{i_{2}}$ = $a_{i_{2}} - a_{i_{3}}$ = ... = $a_{i_{m-1}} - a_{i_{m}}$ (ta różnica może w szczególności wynosić $0$ ).

Czy potrafisz pomóc nam i przywrócić uśmiech bezpieczeństwa na twarzach stroskanych mieszkańców tych ziem?

Wejście:

Pierwsza linia wejścia zawiera dwie liczby - liczbę $n$ oznaczającą liczbę wież w ciągu oraz liczbę $k$ - oznaczającą pozycję wieży maga w ciągu (wieże numerowane są kolejno od $1$ do $n$ ). ( $1 \leq n \leq 10^5, 1 \leq k \leq n$ ). W kolejnej linii znajduje się $n$ liczb całkowitych $a_{1}$ , ..., $a_{n}$ - są to wysokości kolejnych wież $0 \leq a_{i} \leq 10^{6}$ .

Wyjście:

Wyjście powinno zawierać jedną liczbę - długość najdłuższego podciągu arytmetycznego ciągu $a_{1}$ , ... , $a_{n}$ , który zawiera element $a_{k}$ (wieżę maga)

Przykład:

Wejście:

9 4

12 5 9 6 7 8 3 2 0

Wyjście:

(szukany podciąg to 12,9,6,3,0 - wieża maga ma wysokość 6)

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Pozycja	Imię i nazwisko	Wynik	Czas	Wieża strażnicza
1	Damian Straszak	10	02:50:54	10
2	Wojtek Nadara	10	13:55:15	10
3	Witold Długosz	10	55:15:10	10
4	Przemysław Derengowski	10	65:56:58	10
5	Wojciech Szałapski	10	83:04:54	10
6	Krzysztof Pszeniczny	10	202:17:13	10
7	Bartłomiej Gajewski	10	320:25:18	10
8	Kamil Dębowski	8	11:26:20	8
9	Bartosz Tarnawski	8	14:09:58	8
10	Piotr Bejda	8	155:29:43	8
11	Krzysztof Drab	5	36:14:45	5