Сегодня на уроке класс Васи проходил различные алгоритмы кодирования данных. Однако, уже придуманные алгоритмы кодирования его не заинтересовали, и он решил придумать свой собственный. Первый метод, который пришел ему в голову,...
Сегодня на уроке класс Васи проходил различные алгоритмы кодирования данных. Однако, уже придуманные алгоритмы кодирования его не заинтересовали, и он решил придумать свой собственный. Первый метод, который пришел ему в голову, выглядел так: каждый символ строки, состоящей из латинских строчных символов, кодируется числом от 1 до 26 в обратном алфавитном порядке (символ 'a' кодируется числом 26, символ 'b' — числом 25, и т.д.), а затем все эти числа записываются в одну строку подряд без пробелов. Например, строка abza будет закодирована следующим образом: 2625126.
Все бы ничего, но Васин метод оказался не очень эффективен — полученное закодированное сообщение не всегда можно единственным образом декодировать. Однако, Вася решил, что это не такая большая проблема — вместо этого он решил по полученному коду восстанавливать строку минимальной возможной длины. Если таких строк несколько, ему все равно, какую из них он найдет. Помогите ему с этой задачей.
Формат входного файла
В первой строке входного файла input.txt записана строка, состоящая из цифр. Ее длина не превосходит 100.
Гарантируется, что строка получена в результате применения Васиного алгоритма кодирования к некоторой строке, состоящей только из строчных латинских букв.
Формат выходного файла
В выходной файл output.txt требуется вывести раскодированную строку — строку, после применения к которой алгоритма Васи, получается строка, данная во входном файле. Из всех возможных вариантов таких строк, строка в ответе должна иметь минимальную возможную длину. Если строк минимальной длины несколько, разрешается вывести любую их них.
Пример входных и выходных данных
input.txt_____output.txt_______Комментарий
219_________yh____________ Символ 'y' кодируется в число 2, а символ 'h' в число 19. Также правильным ответом является строка "fr".
271________ ytz_____________Других вариантов декодирования нет.
Гость
Ответ(ы) на вопрос:
ГостьБудем последовательно решать задачу для первых i символов кода, основываясь на ответах для i - 1 и i - 2. Заметим, что если i-й символ кода равен 0 или ответа для i - 1 не существует, то ответ для i получается добавлением одного символа к ответу для i - 2, если последние две цифры кода нельзя понять, как зашифрованную букву, или ответа для i - 2 не существует, то надо добавить символ к i - 1, а иначе сравнить длины ответов и добавить букву к тому, кто короче.
Код (python 3.5):
codes = ".zyxwvutsrqponmlkjihgfedcba"
with open('input.txt', 'r') as f:
encoded = list(map(int,list(f.read())))
if len(encoded) == 1:
print(codes[encoded[0]])
else:
decoded = [codes[encoded[0]], ""]
for i in range(1, len(encoded)):
if (decoded[0] is None) or (encoded[i] == 0):
decoded = [decoded[1] + codes[10*encoded[i-1] + encoded[i]], decoded[0]]
elif (10*encoded[i-1] + encoded[i]>26) or (decoded[1] is None) or \
(len(decoded[1]) >= len(decoded[0])):
decoded = [decoded[0] + codes[encoded[i]], decoded[0]]
else:
decoded = [decoded[1] + codes[10*encoded[i-1] + encoded[i]], decoded[0]]
with open('output.txt', 'w') as f:
f.write(decoded[0])
Не нашли ответ?
Похожие вопросы