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

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

Условие

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

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

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

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

Выходной файл должен содержать три целых числа — два различных номера строк, расстояние между которыми наименьшее, и само расстояние. Строки нумеруются от 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
2 15 1

0.081s 0.015s 15