Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Редактор

(Время: 1 сек. Память: 16 Мб Сложность: 65%)

В рамках программы импортозамещения Вам поручено разработать один из модулей будущего отечественного текстового редактора. Модуль должен вычислять расстояние между двумя строками. Редактор умеет выполнять две операции:

  1. Удалить несколько последовательных символов из строки X.
  2. Вставить несколько последовательных символов в строку X.

Стоимость каждой операции равна квадратному корню из K, где K – количество вставленных или удаленных символов. Расстояние между строками X и Y вычисляется как минимальная стоимость операций, необходимых, чтобы превратить X в Y.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральные числа N и M (N, M ≤ 200) – длины строк X и Y. Следующие две строки содержат X и Y, состоящие из заглавных букв английского алфавита.

Выходные данные

В выходной файл OUTPUT.TXT выведите расстояние между X и Y с двумя знаками после десятичной точки.

Пример

INPUT.TXTOUTPUT.TXT
14 4
ACDD
ADGD
2.00

Пояснение

Чтобы превратить строку «ACDD» в «ADGD», необходимо выполнить две операции: «ACDD → ADD → ADGD», а именно: удаление одного символа «C» и вставку одного символа «G». Соответственно, расстояние равно 2.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 A. Классический латинский алфавит
 B. Забег
 C. Гена атакует
 D. Редактор
 E. Максимальное число
 F. Лондонские улицы
 G. Окружность
 H. Юбилей

Красноярский краевой Дворец пионеров, (c)2006 - 2023, E-mail: admin@acmp.ru