Fişierul intrare/ieşire:poly.in, poly.outSursăAutumn Warmup 2006
AutorVlad DumitriuAdăugată de
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Poly

Poly, o fetita careia ii place matematica, a vazut urmatoarea multime: {2, 3, 7, 11, 19, 23, 37}. La un moment dat ea scrie pe o foaie N numere intregi oarecare. Poly, vazand multimea gasita de ea si sirul de N numere s-a intrebat care ar fi subsirul de lungime maxima, unde oricare doua elemente adiacente (din subsir) au cel mai mare divizor comun un numar care nu se divide cu nici un numar din multimea vazuta de ea: {2, 3, 7, 11, 19, 23, 37}. Chiar daca este talentata la matematica, si-a dat seama ca are nevoie de un program pe calculator.

Cerinta

Dandu-se N, numarul de elemente ale sirului scris de ea si sirul propriu-zis, se cere lungimea subsirului maximal cu proprietatile de mai sus.

Date de intrare

Pe prima linie a fiserului poly.in se gaseste numarul N. A doua linie contine N numere separate printr-un singur spatiu.

Date de iesire

Fiserul poly.out v-a contine un singur numar care reprezinta raspunsul.

Restrictii si precizari

  • 2 ≤ N ≤ 30000
  • Numerele din sir sunt cuprinse intre 2 si 108
  • Pentru 40% din teste, N ≤ 1000

Exemplu

poly.inpoly.out
5
2 2 3 4 5
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content