Fişierul intrare/ieşire:s2c.in, s2c.outSursăad-hoc
AutorIonel-Vasile Pit-RadaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

S2C

Fie un şir format din N numere naturale nenule: a[1], a[2], ..., a[N]. Se numeşte subşir 2-crescător de lungime k al şirului dat orice subşir a[x1], a[x2], ..., a[xk], unde 1 ≤ x1 < x2 < ... < xk ≤ N, în care este îndeplinită următoarea proprietate:

  • a[xi] < a[xi+2], pentru orice i, 1 ≤ i ≤ k - 2, adică a[x1] < a[x3] < a[x5] < ... şi a[x2] < a[x4] < a[x6] < ...

Cerinţă

Date fiind T şiruri conform enunţului, se cere să se determine lungimea maximă a câte unui subşir 2-crescător pentru fiecare dintre cele T şiruri date.

Date de intrare

În fişierul de intrare s2c.in se află pe prima linie numărul T, reprezentând numărul de şiruri, iar pe fiecare dintre următoarele 2*T linii se află descrierile şirurilor. Pe linia 2*i se va afla un singur număr natural reprezentând numărul de elemente Ni al celui de-al i-lea şir de numere dat. Pe linia 2*i+1 se vor afla Ni numere naturale, reprezentând numerele din şir, separate prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire s2c.out se vor scrie T linii, fiecare conţinând un singur număr natural. Pe linia i se va scrie un număr natural reprezentând lungimea maximă a unui subşir 2-crescător al celui de-al i-lea şir din cadrul celor T şiruri date.

Restricţii şi precizări

  • 1 ≤ T ≤ 10
  • 1 ≤ Ni ≤ 2.000, pentru fiecare i, 1 ≤ i ≤ T.
  • Pentru 30% din punctaj 1 ≤ Ni ≤ 400, pentru fiecare i, 1 ≤ i ≤ T.
  • Pentru 60% din punctaj 1 ≤ Ni ≤ 1.000, pentru fiecare i, 1 ≤ i ≤ T.
  • Elementele din fiecare şir sunt numere naturale nenule din mulţimea {1, 2, 3, ..., 30.000}.

Exemplu

s2c.ins2c.outExplicaţii
2
8
1 1 3 2 5 3 4 5
5
9 6 4 2 7
6
3
Avem T = 2 teste.
Primul şir are lungimea egală cu 8. Subşirurile 2-crescătoare de lungime maximă, egală cu 6, sunt:
 
1 1 3 2 5 3
1 1 3 2 5 4
1 1 3 2 5 5
1 1 3 2 4 5
1 1 2 3 4 5
 
Al doilea şir are lungimea 5. Subşirurile 2-crescătoare de lungime maximă, egală cu 3, sunt:
 
6 4 7
6 2 7
4 2 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici