Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_AA_11 - Ciąg serpentynowy |
Dany jest ciąg a o rozmiarze n składający się z liczb naturalnych.
Ciągiem serpentynowym b o rozmiarze m nazwiemy dowolny podciąg ciągu a, którego elementy spełniają poniższe równania:
- b1 + 1 = bm
- bm + 1 = b2
- b2 + 1 = bm - 1
- bm - 1 + 1 = b3
- ...
Podciąg ten nie musi być spójny. Gdybyśmy narysowali linię łącząc elementy ciągu w kolejności rosnącej to utworzy nam się serpentyna zwężająca się do środka, stąd jego nazwa.
Przykładowe ciągi serpentynowe:
- 3 5 7 9 10 8 6 4
- 1 3 5 4 2
- 1000000
Odpowiedz na pytanie, jaka jest długość najdłuższego ciągu serpentynowego zawartego w ciągu a?
Wejście
W pierwszej linii wejścia znajduje się liczba n (1 ≤ n ≤ 1000000) określająca rozmiar ciągu a.
W drugiej linii znajduje się n liczb naturalnych z przedziału [1, 1000000], są to elementy ciągu a.
Wyjście
Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest długość najdłuższego ciągu serpentynowego zawartego w ciągu a?
Przykład
Wejście:
12 9 1 3 2 5 7 8 9 10 6 4 5
Wyjście:
6
Wyjaśnienie do przykładu:
Elementy wchodzące w skład najdłuższego ciągu serpentynowego zostały wyróżnione poniżej pogrubioną czcionką:
9 1 3 2 5 7 8 9 10 6 4 5
Spełniają one założenia ciągu serpentynowego o rozmiarze m = 6:
- 3 (b1) + 1 = 4 (b6)
- 4 (b6) + 1 = 5 (b2)
- 5 (b2) + 1 = 6 (b5)
- 6 (b5) + 1 = 7 (b3)
- 7 (b3) + 1 = 8 (b4)
Dodane przez: | Maciej Boniecki |
Data dodania: | 2021-04-19 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |