Редактор
(Время: 1 сек. Память: 16 Мб Сложность: 65%)
В рамках программы импортозамещения Вам поручено разработать один из модулей будущего отечественного текстового редактора. Модуль должен вычислять расстояние между двумя строками. Редактор умеет выполнять две операции:
- Удалить несколько последовательных символов из строки X.
- Вставить несколько последовательных символов в строку X.
Стоимость каждой операции равна квадратному корню из K, где K – количество вставленных или удаленных символов. Расстояние между строками X и Y вычисляется как минимальная стоимость операций, необходимых, чтобы превратить X в Y.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральные числа N и M (N, M ≤ 200) – длины строк X и Y. Следующие две строки содержат X и Y, состоящие из заглавных букв английского алфавита.
Выходные данные
В выходной файл OUTPUT.TXT выведите расстояние между X и Y с двумя знаками после десятичной точки.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 4
ACDD
ADGD | 2.00 |
Пояснение
Чтобы превратить строку «ACDD» в «ADGD», необходимо выполнить две операции: «ACDD → ADD → ADGD», а именно: удаление одного символа «C» и вставку одного символа «G». Соответственно, расстояние равно 2.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
