Fişierul intrare/ieşire:subgeom.in, subgeom.outSursăONI 2008, clasa a 10-a
AutorAndrei GrigoreanAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.1 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subgeom

Miruna tocmai a invatat la ora de matematica despre progresii geometrice. Un sir de numere naturale nenule se numeste progresie geometrica daca este respectata una dintre urmatoarele doua conditii:

  • Sirul este format dintr-un singur element.
  • Daca sirul este format din N (N > 1) elemente v1, v2, ..., vN, atunci exista un numar intreg K mai mare strict decat 1 astfel incat raportul oricaror doua elemente consecutive din sir este egal cu K. Altfel spus, oricare ar fi un indice i, 1 ≤ i < N, vi+1 / vi = K.

Miruna are o imaginatie bogata, asa ca inventeaza o notiune nemaintalnita pana acum - cea de subsir geometric: dandu-se un sir de numere naturale nenule, un subsir care este progresie geometrica se numeste subsir geometric.

Cerinta

Scrieti un program care pentru un sir de N elemente afiseaza lungimea celui mai lung subsir geometric al sau.

Date de intrare

Fisierul de intrare subgeom.in va contine pe prima linie numarul natural T reprezentand numarul de seturi de date din fisier. Fiecare dintre urmatoarele T linii contine un set de date, sub forma:

N v1 v2 ... vN

Prima valoare este un numar natural N, reprezentand numarul de elemente din sir, urmat de cele N numere naturale nenule ce alcatuiesc sirul, separate prin cate un spatiu.

Date de iesire

Fisierul de iesire subgeom.out va contine T linii, cate o linie pentru fiecare set de date. Linia i contine un numar natural reprezentand lungimea maxima a unui subsir geometric al sirului descris pe linia i + 1 in fisierul de intrare.

Restrictii si precizari

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 5000
  • Pentru 40% din teste 1 ≤ N ≤ 128
  • Elementele sirului sunt numere naturale din intervalul [1, 105]
  • Un subsir al unui sir v1 v2 ...vN este format din elemente ale sirului considerate in ordinea in care acestea apar in sir: vi1 vi2... vik (1 ≤ i1 < i2 < ... < ik ≤ N).

Exemplu

subgeom.insubgeom.out
6
3 5 3 7
3 8 4 2
3 4 4 4
3 5 1 10
4 1 2 3 9
5 6 2 8 6 18
1
1
1
2
3
3

Explicatie

Pentru primele trei teste toate subsirurile geometrice au lungimea 1.

Pentru al patrulea test solutia este formata din subsirul 5, 10.

Pentru al cincilea test solutia este formata din subsirul 1, 3, 9.

Pentru ultimul test solutia este formata din subsirul 2, 6, 18.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content