Fişierul intrare/ieşire:fpwl.in, fpwl.outSursăFMI No Stress 2012
AutorDin FolclorAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test3 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fpwl

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 este <,>,=,<,>.

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 fpwl.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 fpwl.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

fpwl.infpwl.out
7 3
2 4 3 1 3 5 3
< > =
6
2 4 3 3 5 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content