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

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

HotLog


 

Расшифровка

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

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

Мария Ивановна подозревает, что записка – это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Оли не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.

Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Оли. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.

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

В первой строке входного файла INPUT.TXT задана длина каждой из строк N (1 ≤ N ≤ 2 000 000) и K – количество возможных ответов на каждый вопрос (1 ≤ K ≤ 52). Ответы нумеруются в порядке abcde...xyzABCDE...XYZ. То есть, при K = 6 множество возможных ответов выглядит как abcdef, а при K = 30 – abcde...xyzABCD.

Во второй строке задана зашифрованная записка – строка, состоящая из строчных и заглавных английских букв.

В третьей строке заданы правильные ответы – строка той же длины, что и первая, состоящая из строчных и заглавных английских букв.

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

В первой строке выходного файла OUTPUT.TXT выведите единственное число – максимально возможное количество правильных ответов у Оли.

Во второй строке выведите расшифровку – строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.

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

Примеры

INPUT.TXTOUTPUT.TXT
110 2
aaabbbaaab
bbbbabbbbb
7
ba
210 2
aaaaaaabbb
bbbbaaabbb
6
ab
39 4
dacbdacbd
acbdacbda
9
cdba

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Банкет
 B. Совершенно секретно
 C. Кубики
 D. Задача о назначениях
 E. Расшифровка

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



Ставки на биатлон