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 | Calin Stefan Georgescu • calingeorgescu |
Timp de execuție pe test | 1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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]. |