Fișierul intrare/ieșire s2c.in, s2c.out Sursă ad-hoc
Autor Ionel-Vasile Piț-Rada Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 1.5 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in s2c.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii