Криптография

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

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

∑_c|e_c – p_c|

Здесь через e_c и p_c обозначены частоты символа c, рассчитанные для среднего текста и для записки, получающейся из зашифрованного текста после применения данной перестановки.

Требуется по заданным частотам написать программу, расшифровывающую закодированное послание.

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

В первой строке входного файла INPUT.TXT записаны два целых числа – N и M (1 ≤ N ≤ 26, 1 ≤ M ≤ 10⁵). Следующие N строк задают буквы, которые, по сведениям Кристины, могли встречаться в исходном тексте. Соответствующая буква c_i – первый символ строки, через пробел от него записана частота этой буквы p_i, заданная с 4 знаками после десятичной точки. Все p_i неотрицательны, а их сумма равна 1. Последняя строка содержит M символов – текст, который необходимо расшифровать. Исходный и зашифрованный текст состоит из строчных английских букв.

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

В выходной файл OUTPUT.TXT выведите N символов по одному на строке, которые, если верить описанному методу, должны быть сопоставлены символам из входного файла. Если оптимальных решений несколько, выведите любое из них.

Пример

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

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