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

14.03.2011 - Damian Rusak
TrudnośćTrudność

 

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:

5

(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.
PozycjaImię i nazwiskoWynikCzasWieża strażnicza
1Damian Straszak1002:50:5410
2Wojtek Nadara1013:55:1510
3Witold Długosz1055:15:1010
4Przemysław Derengowski1065:56:5810
5Wojciech Szałapski1083:04:5410
6Krzysztof Pszeniczny10202:17:1310
7Bartłomiej Gajewski10320:25:1810
8Kamil Dębowski811:26:208
9Bartosz Tarnawski814:09:588
10Piotr Bejda8155:29:438
11Krzysztof Drab536:14:455
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com