Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | Invalid task identifier .in, Invalid task identifier .out | Sursă | Invalid task identifier |
Autor | Invalid task identifier | Adăugată de | Invalid task identifier |
Timp execuţie pe test | Invalid task identifier sec | Limită de memorie | Invalid task identifier kbytes |
Scorul tău | Invalid task identifier | Dificultate | Invalid task identifier |
Vezi solutiile trimise | Statistici
Invalid task identifier
Pentru un sir de numere a1,a2,...,aN notam secventa poloneza a sa ca fiind secventa s1,s2,...,sN-1 de simboluri <, > sau =. Simbolul si al secventei reprezinta relatia dintre ai si ai+1. De exemplu secventa poloneza a sirului 2,4,3,3,5,3 e <,>,=,<,>.
Spunem ca sirul b1,b2,...,bN+1 cu secventa poloneza s1,s2,...,sN realizeaza o alta secventa poloneza s'1,s'2,...,s'K daca oricare ar fi i de la 1 la N si=s'(i-1) mod K + 1. Altfel spus secventa s1,s2,...,sN se poate obtine din secventa s'1,s'2,...,s'K repetand aceasta secventa de cateva ori si apoi eliminand sufixul corespunzator. De exemplu secventa 2,4,3,3,5,3 realizeaza urmatoarele secvente poloneze:
- <,>,=
- <,>,=,<,>
- <,>,=,<,>,<,<,=
- <,>,=,<,>,=,>,>
si multe altele.
Vi se da un sir de numere a1,a2,...,aN si o secventa poloneza s1,s2,...,sK. Voi trebuie sa aflati cel mai lung subsir al lui a ai1,ai2,...,aiM (1≤i1≤i2≤..≤iM) care realizeaza secventa poloneza s.
Date de intrare
Prima linie a fisierului fpvl.in contine pe prima linie 2 numere intregi N si K separate printr-un singur spatiu reprezentand lungimea sirului (ai), respectiv (sj)
A doua linie contine N numere intregi a1,a2,...,aN separate prin cate un spatiu reprezentand sirul a.
A treia si ultima linie contine K simboluri de forma <,> sau = reprezentand secventa poloneza s
Date de ieşire
În fişierul de ieşire fpvl.out trebuie sa contina 2 linii.
Pe prima linie trebuie sa se gaseasca M, lungimea celui mai lung subsir al lui a care realizeaza secventa poloneza s.
A doua si ultima linie trebuie sa contina M elemente ai1,ai2,...,aiM reprezentand un astfel de subsir.
Restricţii
- 1 ≤ N, K ≤ 500.000
- 1 ≤ ai ≤ 1.000.000
Exemplu
fpvl.in | fpvl.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...