Fişierul intrare/ieşire:scmax2.in, scmax2.outSursăIIOT 2019-20 Runda 3
AutorAlexandru PetrescuAdăugată devladttturcuman vlad vladtt
Timp execuţie pe test0.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.inscmax2.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?