Fișierul intrare/ieșire | s2c.in, s2c.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Ionel-Vasile Piț-Rada | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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 |