Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача D. Динамика

Задачу добавил: alef

Успешно сдано решений: 63

Время на тест 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



Задача D.

Сдать задачу

Задать вопрос жюри по этой задаче