13/04/2025 15:02:59

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2815. Песня сирен

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Прежде всего ты сирен повстречаешь, которые пеньем
Всех обольщают людей, какой бы ни встретился с ними.
Кто, по незнанью приблизившись к ним, их голос услышит,
Тот не вернется домой никогда.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 12

Корабль Одиссея проплывает мимо скал, населенных сладкоголосыми сиренами. Сирены непрерывно и бесконечно поют свою песню, раз за разом повторяя одну и ту же последовательность нот длины $N$ . Несколько звучащих подряд нот могут образовать заклинание длины $M$ , которое лишает разума любого слушателя на время $T$ . То есть, если ноты с номерами от $i-M+1$ до $i$ включительно образуют заклинание, то во время звучания следующих $T$ нот (с $i+1$ по $i+T$ включительно) все гребцы Одиссея бросают весла и корабль не двигается. После окончания действия заклинания гребцы сразу же (в начале звучания ноты с номером $i+T+1$ ) приходят в себя и возвращаются к работе, если только не попадут под действие заклинание снова. Если в момент срабатывания заклинания гребцы уже лишены разума, заклинание все равно действует (см. пример). Чтобы пересечь опасный участок моря, на котором слышно пение сирен, нужно проработать веслами в общей сложности в течение времени $L$ . Определите, сколько времени на это потребуется кораблю Одиссея.

В первой строке ввода указано 4 натуральных числа: число нот в песне $N$ , число нот в заклинании $M$ ( $1<=N,M<=10^5$ ), время действия заклинания $T$ ( $1<=T<=10^10$ ) и необходимое время гребли L ( $1<=L<=10^10$ ). Время измеряется в единицах, равных продолжительности звучания одной ноты. Вторая строка содержит $N$ строчных латинских букв - ноты, содержащиеся в песне сирен. Третья строка содержит $M$ строчных латинских букв - ноты, образующие заклинание.

Выведите единственное целое число – время, которое потребуется кораблю для преодоления опасного участка. Если корабль попадет в плен к сиренам навечно, выведите -1.

Пример ввода 1

3 4 2 8
aab
abaa

Пример вывода 1

Пример ввода 2

3 1 4 4
abc
c

Пример вывода 2

-1

Пояснение к примеру 1. Песня будет звучать так: aabaabaabaabaab… Заклинание впервые сработает в конце 5-й ноты (т.к. символы со 2-го по 5-й равны "abaa"), поэтому в течение 6-й и 7-й нот гребцы бездействуют. Затем на 8-й ноте гребцы снова гребут, а на 9-й и 10-й бездействуют (из-за того, что ноты с 5-й по 8-ую вновь равны "abaa"). Затем заклинание будет срабатывать в конце 11-ой, 14-ой и т.д. нот. Гребцы будут грести в следующие ноты: 1, 2, 3, 4, 5, 8, 11, 14. В конце 14-ой ноты накопленная продолжительность гребли достигает 8, и корабль покидает опасный участок.