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

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

HotLog


 

Строки - 4

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

Определим расстояние между равными по длине строками SA и SB (обозначим d(SA, SB)) как сумму для всех 1 ≤ i ≤ |SA| кратчайших расстояний между буквами SA(i) и SB(i) в циклически замкнутом английском алфавите (т.е. после буквы «a» идет буква «b», ..., после буквы «z» идет «a»). Например d(aba, aca) = 1, а d(aba, zbz) = 2.

Напомним, что циклическим сдвигом строки S называется строка (обозначим, как S→k) Sk+1Sk+2Sk+3 ... S|S|S1S2 ... Sk для некоторого k, где |S| – длина строки S.

Степенью циклического расстояния между строками SA и SB (|SA| = |SB|) называется сумма:

Требуется посчитать степень циклического расстояния заданных строк SA и SB.

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

Входной файл INPUT.TXT содержит две строки равной длины, не превышающей 105 символов. Строки состоят только из маленьких букв английского алфавита.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
1a
b
1
2ab
ac
8

Пояснение

Во втором примере все циклические сдвиги строки «ab»: «ab» и «ba», все циклические сдвиги строки «ac»: «ac» и «ca». Искомое значение равно:

d(ab, ac) + d(ab, ca) + d(ba, ac) + d(ba, ca) = 1 + 3 + 3 + 1 = 8


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

[Обсуждение] [Все попытки] [Лучшие попытки]

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