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.
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
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.
Î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
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.
În fişierul de ieşire $s2c.out$ ...
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 |_. 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
|
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
...
== include(page="template/taskfooter" task_id="s2c") ==
