Fişierul intrare/ieşire:progr.in, progr.outSursăONIS 2014, Runda 2
AutorTeodor PlopAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.5 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/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.inprogr.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content