Модуль: Жадные алгоритмы


Задача

3 /9


Прошутто покупает кулон

Задача

Прошутто очень любит носить кулоны. Особенно ему нравятся те, что с надписями слов, состоящих из строчных латинских букв, поэтому только такие он и носит.
Прошутто захотел приобрести себе новый кулон и отправился в специальный магазин. 
В магазине ему рассказали, что особенно в моде сейчас кулоны с надписями-палиндромами. Конечно же Прошутто решил подобрать себе такой, однако не смог определиться с выбором.
Тогда ему поведали древний обычай, который гласит, что нужно взять слово из надписи на текущем кулоне, придумать приятное слово той же длины и трансформировать их в слово для надписи на новом кулоне.

Операция трансформации происходит следующим образом:
1) Символам, стоящим на соответствующих позициях присваиваются номера, которые соответствуют позициям этих символов в алфавите. Так букве d будет соответствовать номер 4, а букве a - 1.
2) Номера на соответствующих позициях складываются. Если сумма превышает размер латинского алфавита, то из нее вычитают 26.
3) В новое слово добавляется буква, которой сопоставляется полученная сумма.
Таким образом слова "aba" и "bab" трансформируются в "ccc", а "zxc" и "bbb" в "bze".

У Прошутто сейчас кулон с надписью s длины n, но приятные слова не приходят ему на ум. Однако он подумал, что было бы интересно взять лексикографически минимальное слово для трансформации текущей надписи в модную надпись-палиндром.
Не смотря на то, что текущий кулон Прошутто мог уже иметь надпись-палиндром, Прошутто все равно хочет выбрать себе новый.

Прошутто сегодня мало спал, поэтому не может определить с каким словом ему нужно трансформировать текущую надпись. Помогите ему, пожалуйста.

Входные данные:
В первой строчке находится натуральное число n (1 ≤ n ≤ 105) - длина надписи на текущем кулоне Прошутто.
Во второй строчке находится строка s - сама надпись.

Выходные данные:
Выведите единственную строку - слово той же длины, с которым нужно трансформировать имеющуюся надпись, чтобы получить надпись-палиндром.

Примеры:
 
Входные данные Выходные данные
2
ad
ax
7
abacaba
aaaaaaa

Пояснение:
В первом примере слово "ax" - лексикографически минимальное, с которым можно трансформировать имеющуюся надпись "ad", чтобы получить надпись-палиндром (это будет "bb").


time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6421
Python8
Комментарий учителя