Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-05-11 10:19:44.
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.infpvl.out
7 3
2 4 3 1 3 5 3
< > =
6
2 4 3 3 5 3

Explicaţie

...

Invalid task identifier

Cum se trimit solutii?