Fișierul intrare/ieșire padure.in, padure.out Sursă Cursul IQ Academy 2017
Autor Călin-Ștefan Georgescu | Cristian Frâncu Adăugată de avatar calingeorgescu Calin Stefan Georgescu calingeorgescu
Timp de execuție pe test 1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Pădure (clasa a 5-a)

Ionel s-a rătăcit prin pădure și a ajuns la o răscruce păzită de un bătrân. Bătrânul i-a zis că îi arată drumul să iasă din pădure dacă îi dă răspunsul la următoarea problemă : dat fiind un șir de n numere, se cere să se afle care este cea mai lungă secvență cu proprietatea că oricare două numere aflate pe poziții consecutive în secvență se împart la același număr d, iar d este diferit de 1. Ionel nu știe răspunsul la această întrebare și vă roagă pe voi să îl ajutați.

Cerință

Scrieți un program care va rezolva problema lui Ionel pentru ca acesta să poată ieși din pădure.

Date de intrare

Fișierul de intrare padure.in conține pe prima linie numărul n, reprezentând numărul de numere din șir, iar pe a doua linie se află n numere, reprezentând șirul dat de bătrân.

Date de ieșire

În fișierul de ieșire padure.out se va afla un singur număr, reprezentând răspunsul la problema dată lui Ionel.

Restricții

  • 2 ≤ n ≤ 100000
  • toate numerele din șir sunt numere naturale între 2 și două miliarde

Exemplu

padure.in padure.out Explicație
10
18 27 15 28 34 39 14 74 111 57
4
18 și 27 se împart la 3. 27 și 15 se împart la 3. 15 și 28 nu se
împart la nimic în afară de 1. 28 și 34 se împart la 2. 34 și 39
nu se împart la nimic în afară de 1. La fel și 39 și 14. 14 și 74
se împart la 2. 74 și 111 se împart la 37. 111 și 57 se împart la 3.
 
Secvențele din șir sunt: [18 27 15], [28 34], [39], [14 74 111 57].
Secvența de lungime maximă are 4 numere: [14 74 111 57].
8
15 10 14 49 4 9 77 21
4
Secvențele din șir sunt: [15 10 14 49], [4], [9], [77 21]
Secvența de lungime maximă are lungime 4: [15 10 14 49].

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii