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

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

HotLog


 

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

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

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

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

c|ec – pc|

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
13 5
t 0.1667
r 0.5000
q 0.3333
ecere
r
e
c

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483