.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » subgeom

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
subgeom


Timp maxim de execuţie / test:
0.3s
Memorie totala disponibilă / stivă:
2MB / 1MB

Miruna tocmai a învăţat la ora de matematică despre progresii geometrice. Un şir de numere naturale nenule se numeşte progresie geometrică dacă este respectată una dintre următoarele două condiţii:
- Şirul este format dintr-un singur element.
- Dacă şirul este format din N (N>1) elemente v1 v2 ...vN, atunci există un număr întreg K mai mare strict decât 1 astfel încât raportul oricăror două elemente consecutive din şir este egal cu K. Altfel spus, oricare ar fi un indice i, 1 ≤ i < N, vi+1/vi = K.
Miruna are o imaginaţie bogată, aşa că inventează o noţiune nemaîntâlnită până acum - cea de subşir geometric: dându-se un şir de numere naturale nenule, un subşir care este progresie geometrică se numeste subşir geometric.

Cerinţă

Scrieţi un program care pentru un şir de N elemente afişează lungimea celui mai lung subşir geometric al său.

Date de intrare

Fişierul de intrare subgeom.in va conţine pe prima linie numărul natural T reprezentând numărul de seturi de date din fişier. Fiecare dintre următoarele T linii conţine un set de date, sub forma:
N v1 v2 ...vN
Prima valoare este un număr natural N, reprezentând numărul de elemente din şir, urmat de cele N numere naturale nenule ce alcătuiesc şirul, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire subgeom.out va conţine T linii, câte o linie pentru fiecare set de date. Linia i conţine un număr natural reprezentând lungimea maximă a unui subşir geometric al şirului descris pe linia i+1 în fişierul de intrare.

Restricţii

1 ≤ T ≤ 10
1 ≤ N ≤ 5000

Pentru 40% din teste 1 ≤ N ≤ 128
Elementele şirului sunt numere naturale din intervalul [1, 105]
Un subşir al unui şir v1 v2 ...vN este format din elemente ale şirului considerate în ordinea în care acestea apar în şir: vi1 vi2... vik (1≤i1<i2<...<ik≤N).

Exemple

subgeom.insubgeom.outExplicaţii
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 Pentru primele trei teste toate subşirurile geometrice au lungimea 1.
Pentru al patrulea test soluţia este formată din subşirul 5, 10.
Pentru al cincilea test soluţia este formată din subşirul 1, 3, 9.
Pentru ultimul test soluţia este formată din subşirul 2, 6, 18

autor: Stud. Andrei Grigorean
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2008: ab2, iepuras, palind, auto, div, teatru, pm, submat, reteta2, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: fbr, 2sir, platforma, barfa, sumdif, cartonase, desen, seif, kinder, shgraf, pikachu, dist1, submatrix1, teroristi, parpal, bubblesort
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor