Задача D. Динамика
Задачу добавил: alef
Успешно сдано решений: 68
Время на тест 2 с, память 256 Мб
Отдел ZZZ занимается необычным исследованием. В распоряжении института оказался органический материал с многообещающими свойствами. Молекула этого материала описывается последовательностью строчных латинских букв, кодирующих ее фрагменты.
Пока получить такой материал в лабораторных условиях затруднительно. Тем не менее сотрудники отдела напряженно работают и получили уже три молекулы, похожие на нужную.
Определим показатель сходства для фрагмента #J следующим образом. Если на месте #J в последовательности, кодирующей оригинальную молекулу, и в последовательности, кодирующей полученную молекулу, стоят совпадающие буквы, то показатель сходства Kj = 2. Если в полученной молекуле на месте #J стоит буква, соседствующая в алфавите слева или справа с буквой, стоящей на месте #J в оригинальной молекуле, то показатель сходства Kj = 1. Во всех остальных случаях Kj = 0.
Показатель сходства для молекулы определяется как сумма показателей сходств для всех ее фрагментов.
Близится квартальный отчет, и сотрудники хотели бы показать «положительную динамику» исследований. Для этого они хотели бы упорядочить три полученные молекулы по неубыванию показателей сходства и обратились к Кеше за помощью.
Формат входного файла input.txt
Первая строка — целое число N (1 ≤ N ≤ 1000) — длина каждой из молекул.
Вторая строка содержит последовательность из N строчных латинских букв, описывающую оригинальную молекулу.
Третья, четвертая и пятая строки содержат описание молекулы № 1, молекулы № 2 и молекулы № 3, полученных отделом ZZZ. Каждое описание также состоит из N строчных латинских букв.
Формат входного файла output.txt
Первая строка содержит два целых числа через пробел: номер молекулы с наименьшим показателем сходства и ее показатель сходства
Вторая строка содержит два целых числа через пробел: номер молекулы с не наименьшими не наибольшим показателем сходства и ее показатель сходства
Третья строка содержит два целых числа через пробел: номер молекулы с наибольшим показателем сходства и ее показатель сходства.
Если какие-либо молекулы имеют одинаковый показатель сходства, сначала нужно выводить молекулу с меньшим номером.
Пример входного файла
10
gcattagcat
gbbtuzfdas
hijtagcatt
tacgattacg
Пример выходного файла
3 0
2 5
1 12