Codeforces Round 855 (Div. 3) |
---|
Закончено |
Это простая версия задачи. В этой версии $$$k$$$ всегда равно $$$3$$$.
Верховный чародей Визенгамота однажды поймал злого волшебника Drahyrt, но злой волшебник вернулся и хочет отомстить верховному чародею. Поэтому он украл у его ученика Гарри заклинание $$$s$$$.
Заклинание — это строка длины $$$n$$$, состоящая из строчных латинских букв.
Drahyrt хочет заменить заклинание на непростительное заклятие — строку $$$t$$$.
Drahyrt с помощью древней магии может менять местами буквы на расстоянии $$$k$$$ или $$$k+1$$$ в заклинании сколько угодно раз. В этой версии задачи можно менять буквы на расстоянии $$$3$$$ или $$$4$$$. Другими словами, Drahyrt может поменять буквы на позициях $$$i$$$ и $$$j$$$ в заклинании $$$s$$$ если $$$|i-j|=3$$$ или $$$|i-j|=4$$$.
Например, если $$$s = $$$ «talant» и $$$t = $$$ «atltna», то Drahyrt может действовать следующим образом:
Вам даны заклинания $$$s$$$ и $$$t$$$. Может ли Drahyrt изменить заклинание $$$s$$$ на $$$t$$$?
В первой строке входных данных дано единственное целое число $$$T$$$ ($$$1 \le T \le 10^4$$$) — количество наборов входных данных в тесте.
Далее следуют описания наборов входных данных.
В первой строке содержится два целых числа $$$n, k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$k = 3$$$) — длина заклинаний и число $$$k$$$ такое, что Drahyrt может менять буквы в заклинании на расстоянии $$$k$$$ или $$$k+1$$$.
Во второй строке дано заклинание $$$s$$$ — строка длины $$$n$$$, состоящая из строчных латинских букв.
В третьей строке дано заклинание $$$t$$$ — строка длины $$$n$$$, состоящая из строчных латинских букв.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Обратите внимание, что ограничений на сумму значений $$$k$$$ по всем наборам входных данных нет.
Для каждого набора входных данных выведите в отдельной строке «YES» если Drahyrt может изменить заклинание $$$s$$$ на $$$t$$$ и «NO» иначе.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
76 3talantatltna7 3abacabaaaaabbc12 3abracadabraaavadakedavra5 3acciocicao5 3lumosmolus4 3uwjttwju4 3kvpxvxpk
YES YES NO YES NO YES NO
Первый пример разобран в условии.
Во втором примере можно действовать следующим образом:
Во третьем примере можно показать, что из строки $$$s$$$ невозможно получить строку $$$t$$$ меняя местами буквы на расстоянии $$$3$$$ или $$$4$$$.
В четвертом примере подходит например следующая последовательность преобразований:
В пятом примере можно показать, что невозможно получить из строки $$$s$$$ строку $$$t$$$.
В шестом примере достаточно поменять местами две крайние буквы.
Название |
---|