In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Niniejsze zadanie to trudniejsza wersja zadania Monotoniczność z finału XVII OI. Nie wystąpiła ona w samym konkursie.
Schematem monotoniczności ciągu liczb całkowitych
nazwiemy ciąg
złożony ze znaków
,
lub =.
Znak
reprezentuje relację pomiędzy liczbami
i
.
Na przykład, schematem monotoniczności ciągu
jest
.
Powiemy, że ciąg liczb , o schemacie monotoniczności
, realizuje pewien schemat monotoniczności
,
jeżeli dla każdego całkowitego
zachodzi
.
Innymi słowy, ciąg
uzyskujemy, powtarzając odpowiednio
długo ciąg
i ewentualnie odrzucając kilka ostatnich
wyrazów tego powtórzenia.
Na przykład, ciąg
realizuje następujące schematy monotoniczności:
Dany jest ciąg liczb całkowitych .
Twoim zadaniem jest znalezienie najdłuższego jego podciągu
(
)
realizującego pewien zadany schemat monotoniczności
.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite
oraz
(
,
),
oddzielone pojedynczym odstępem i oznaczające odpowiednio długość ciągu
oraz długość schematu monotoniczności
.
W drugim wierszu znajduje się liczb całkowitych
pooddzielanych
pojedynczymi odstępami, oznaczających wyrazy badanego ciągu
(
).
W trzecim wierszu znajduje się znaków
postaci <, > lub =,
pooddzielanych pojedynczymi odstępami, oznaczających kolejne wyrazy schematu monotoniczności.
W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać
jedną liczbę całkowitą oznaczającą maksymalną długość podciągu ciągu
realizującego schemat monotoniczności
.
W drugim wierszu Twój program powinien wypisać dowolny przykład takiego
podciągu , oddzielając jego wyrazy pojedynczymi
odstępami.
Dla danych wejściowych:
7 3 2 4 3 1 3 5 3 < > =
poprawną odpowiedzią jest:
6 2 4 3 3 5 3
Autorzy zadania: Marian M. Kędzierski, Piotr Niedźwiedź.