| Fişierul intrare/ieşire: | scmax2.in, scmax2.out | Sursă | IIOT 2019-20 Runda 3 |
| Autor | Alexandru Petrescu | Adăugată de |  turcuman vlad •vladtt |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Scmax2
Se da un sir de numere. Sa se gaseasca cel mai lung subsir crescator. Formal, sa se elimine un numar cat mai mic de numere in asa fel incat numerele ramase sa formeze un sir strict crescator, si sa se afiseze numarul de numere ramase.
Glumim. Cui i-ar trebui asa ceva in viata reala?
Pe noi ne intereseaza ceva mult mai profund.
Cerinta
Fiecare numar a are un numar preferat Ta, care desi poate fi (dupa regulile obisnuite) Ta ≤ a, numarul a e gata sa considere ca a < Ta, daca asta l-ar aduce pe Ta imediat in dreapta lui a in subsirul crescator pe care il consideram. Adica, pe langa regulile obisnuite care spun cand e un numar mai mic decat altul, introducem relatiile a < Ta (fara sa stergem relatia Ta < a).
Sa se gaseasca subsirul crescator maximal, avand in vedere noile conditii.
Formal, un sir este (mai nou) strict crescator daca pentru fiecare pereche de numere consecutive din sir (left, right), fie left < right fie Tleft = right.
Date de intrare
Fişierul de intrare scmax2.in contine pe prima linie numarul Q de teste din fisier. Pentru fiecare test descrierea e asemanatoare: Pe prima linie numarul natural N de numere din sir. Pe urmatoarea linie se afla N numere naturale cu valori intre 1 si N, reprezentand sirul. Pe urmatoarea linie se afla N numere naturale cu valori intre 1 si N, al i-ulea dintre acestea find Ti.
Date de ieşire
În fişierul de ieşire scmax2.out se afla marimea celui mai lung subsir crescator maximal al sirului, avand in vedere noi reguli.
Restricţii
- 1 ≤ Q ≤ 5
- 1 ≤ N ≤ 50.000
- Pentru 10 puncte, N ≤ 14
- Pentru alte 10 puncte, N ≤ 100
- Pentru alte 10 puncte, Ti = i pentru orice i
- Pentru alte 10 puncte, toate numerele din sir sunt fie 1, fie 2, fie 3
- Pentru alte 10 puncte, pentru fiecare numar a exista cel mult 3 numere b pentru care Tb = a
Exemplu
| scmax2.in | scmax2.out |
|---|---|
| 2 10 4 1 6 1 8 10 10 1 9 1 3 6 3 2 1 9 8 1 5 10 8 8 1 8 6 4 8 5 7 7 3 2 8 8 4 5 6 | 5 6 |
Explicaţie
In primul test secventa maximala este 4 6 8 10 10
In al doilea test secventa maximala este 1 8 6 4 5 7
