Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
1

Задача на предположительно максимальный поток

03.02.2015, 15:58. Просмотров 226. Ответов 0
Метки нет (Все метки)

Доброго времени суток, уважаемые форумчане. ВОзникла сложность с одной задачей и я прошу у вас помощи.
Задача:
Ограничения :
Время работы - 1 секунда
Огрничение по памяти - 256 мб.

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

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

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

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

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

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

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

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

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

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

Если несколько расшифровок дают правильный ответ, выведите любую.


Очень прошу вас помочь!
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2015, 15:58
Ответы с готовыми решениями:

Максимальный поток в неориентированном графе
Какой алгоритм следует использовать для нахождения максимального потока в неориентированном...

Задача на максимальный поток в Visual Basic
У меня есть граф, в нём 25 точек. необходимо решить задачу на максимальный поток. выходим...

Задача на (предположительно) супперпозицию двух распределений
Здравствуйте. Имеется задача: найти вероятность того, что корни уравнения x2+px+10q = 0 будут...

Максимальный поток в графе
доброе время суток, нужно найти максимальный поток с помощью алгоритма Форда-Фалкерсона

Максимальный поток графа
Написал программу для поиска максимального потока в графе. На сайте mmccme.ru некоторые тесты не...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2015, 15:58

Максимальный поток транспортной сети
Друзья, помогите найти максимальный поток транспортной сети

Максимальный поток минимальной стоимости
Вечер добрый, нашел программу работает, выдает как я понял максимальный поток и минимальную...

Максимальный поток; Сетевое планирование
Здравствуйте. Необходимо решить две задачи: 1. Найти максимальный поток 2. Расчитать на графике...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.