Fişierul intrare/ieşire:padure.in, padure.outSursăCursul IQ Academy 2017
AutorCristian Francu, Georgescu Calin StefanAdăugată decalingeorgescuCalin Stefan Georgescu calingeorgescu
Timp execuţie pe test1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inpadure.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici