Fişierul intrare/ieşire: | progr.in, progr.out | Sursă | ONIS 2014, Runda 2 |
Autor | Teodor Plop | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 12288 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Progr
După succesul lui Petrică, a venit şi rândul lui Georgică să se joace cu progresiile aritmetice. Acesta are un vector cu N numere naturale şi se întreabă câte progresii aritmetice maximale cu raţia pozitivă (mai mare decât zero), care au cel puţin doi termeni, poate forma cu aceste numere.
O progresie aritmetică X 1, X 2, ..., X k, cu X 1, X 2, ..., X k aparţinând vectorului este maximală dacă:
- Oricare Y aparţinand vectorului, Y, X 1, X 2, ..., X k nu este progresie aritmetică
- Oricare Y aparţinand vectorului, X 1, X 2, ..., X k, Y nu este progresie aritmetică
Date de intrare
Fişierul de intrare progr.in conţine pe prima linie T, numărul de teste. În continuare, pentru fiecare test, pe prima linie se va găsi un număr natural N, iar pe următoarea linie N numere naturale, având semnificaţia din enunţ.
Date de ieşire
În fişierul de ieşire progr.out se vor găsi T linii, iar fiecare linie i va conţine un singur număr natural, reprezentând numărul de progresii aritmetice care se pot forma cu numerele din testul i.
Restricţii
- T = 10
- 1 ≤ N ≤ 2.000
- 1 ≤ v[i] ≤ 109, unde v[i] este element printre cele N numere ale lui Georgică.
- Se garantează că elementele vectorului sunt distincte.
Exemplu
progr.in | progr.out | Explicaţie |
---|---|---|
1 3 2 3 1 | 2 | Cele două progresii sunt: 1 3, 1 2 3. 1 2 şi 2 3 sunt progresii, dar nu sunt maximale. |