| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP8_2G - Ciąg NWD |
Dany jest ciąg rosnący n liczb naturalnych. Twoim zadaniem jest wyznaczenie długości najdłuższego podciągu, w którym największy wspólny dzielnik każdej pary sąsiadujących elementów jest większy od 1.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1;105] określająca liczbę elementów ciągu. W kolejnej linii znajduje się n liczb naturalnych z zakresu [1;105] będących elementami ciągu. Dla każdej pary sąsiadujących elementów zachodzi nierówność ai < ai + 1.
Wyjście
Na wyjściu należy wypisać długość szukanego podciągu.
Przykład
Wejście
9 2 5 6 7 8 12 15 19 20
Wyjście
6
Wyjaśnienie do przykładu
Najdłuższy podciąg spełniający warunek to: 2, 6, 8, 12, 15, 20. Największe wspólne dzielniki kolejnych par sąsiadujących elementów to: 2, 2, 4, 3, 5.
| Dodane przez: | Maciej Boniecki |
| Data dodania: | 2016-03-18 |
| 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 ASM64 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 |
| Pochodzenie: | VIII Mistrzostwa WWSI w Programowaniu |