Задача B. Минимальное расстояние Левенштейна с частотами

Автор:Бойко   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:10 Мб
Выходной файл:output.txt  

Условие

Дано N строк, состоящих из заглавных латинских букв (аминокислот). Требуется написать программу, определяющую пару строк с наименьшим расстоянием Левенштейна, включающего вставки, удаления и замены символов. Вес удаления/вставки принять равным частоте данной аминокислоты. Частоты округлять до 5-го дробного знака. Замена, соответственно, складывается из суммы частот двух аминокислот.

Формат входного файла

Во входном файле содержатся N строк.

Формат выходного файла

Выходной файл должен содержать три числа (два целых и одно дробное) — два различных номера строк, расстояние между которыми наименьшее, и само расстояние (округлить до 2 дробных знаков). Строки нумеруются от 1 до N.

Ограничения

N = 25. Длина строк не превосходит 1000 символов. Если существует несколько решений, выведите c минимальным N, минимизировать сначала номер, потом второй. Например 1 10, а не 2 9.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
D
PN
LAD
S
RA
NP
AS
A
GPW
EGA
AQ
KY
FKG
GA
N
GPVSLGGLP
YR
G
PEAGPMISK
KGNN
GG
GPWM
NS
AGP
TDQNGG
5 8 0.03

0.065s 0.011s 15