s2c

S2c

== include(page="template/taskheader" task_id="s2c") ==

p<>. 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 &le; x1 &lt; x2 &lt; ... &lt; xk &le; N$ , în care este îndeplinită următoarea proprietate:

p<>. Fie un şir format din $N$ numere naturale nenule: $a&#91;1], a&#91;2], ..., a&#91;N]$.

* $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] < ...$

p<>. Se numeşte subşir $2$-crescător de lungime $k$ al şirului dat orice subşir $a[x{~1~}], a[x{~2~}], ...,a[x{~k~}]$, unde $1 &le; x{~1~} &lt; x{~2~} &lt; ... &lt; x{~k~} &le; N$ , în care este îndeplinită următoarea proprietate:
 
* $a[x{~i~}] &lt; a[x{~i+2~}]$, pentru orice $i, 1 &le; i &le; k - 2$, adică $a[x{~1~}] &lt; a[x{~3~}] &lt; a[x{~5~}] &lt; ...$ şi $a[x{~2~}] &lt; a[x{~4~}] &lt; a[x{~6~}] &lt; ...$
 
h2. Cerinţă
 
p<>. 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.

h2. Date de intrare

Fişierul de intrare $s2c.in$ ...

p<>. Î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 $N{~i~}$ al celui de-al $i$-lea şir de numere dat. Pe linia $2*i+1$ se vor afla $N{~i~}$ numere naturale, reprezentând numerele din şir, separate prin câte un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $s2c.out$ ...

p<>. În fişierul de ieşire $s2c.out$ se va scrie pe fiecare dintre $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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ N{~i~} ≤ 2000, pentru fiecare i, 1 ≤ i ≤ T.$
* $Pentru 30% din punctaj 1 ≤ N{~i~} ≤ 400, pentru fiecare i, 1 ≤ i ≤ T.$
* $Pentru 60% din punctaj 1 ≤ N{~i~} ≤ 1000, pentru fiecare i, 1 ≤ i ≤ T.$
* $Elementele din fiecare şir sunt numere naturale nenule din mulţimea {1, 2, 3, …, 30000}$

h2. Exemplu

table(example). |_. s2c.in |_. s2c.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. s2c.in |_. s2c.out |_. Explicaţie |
| 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
|

...

== include(page="template/taskfooter" task_id="s2c") ==