ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2014

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Декан и расписание

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Приближается новый учебный год, и декану нужно составить расписание занятий для первого курса. Всего в расписании должно быть n пар. За последние годы было сделано интересное наблюдение: студенты прогуливают все пары с чётными номерами и посещают все пары с нечётными номерами (пары нумеруются начиная с единицы). Конечно же, декан хочет, чтобы студенты посетили как можно больше важных пар, поэтому он постарается поставить более важные пары на места с нечётными номерами, а менее важные — на места с чётными номерами. Но так как факультет у нас математико-механический, то к оценке расписания нужно подойти максимально формально.
В расписание первому курсу можно поставить любой из 26 преподаваемых на факультете предметов. Обозначим их строчными латинскими буквами от a до z. Назовём важностью предмета его позицию в английском алфавите, таким образом предмет a будет иметь важность 1, а предмет z — важность 26. Качеством расписания занятий назовём сумму важностей предметов в нём, причём предметы на местах с нечётными номерами входят в эту сумму со знаком плюс, а предметы с чётными номерами — со знаком минус.
К сожалению, административные препятствия ограничивают свободу декана. Во-первых, в расписании должно быть хотя бы k различных предметов, поэтому декану могут не дать поставить на все нечётные места пары по матанализу, а на все чётные — пары по философии. Во-вторых, на некоторых местах должны стоять определённые предметы. Помогите декану составить самое качественное расписание с учётом этих ограничений!

Исходные данные

В первой строке дана строчка длины n (1 ≤ n ≤ 105) из строчных латинских букв и знаков вопроса, задающая предметы, которые уже стоят в расписании. Буквы обозначают эти предметы, а знаки вопроса — свободные пары. Во второй строке дано целое число k (1 ≤ k ≤ 26) — минимальное количество различных предметов в расписании.

Результат

Если невозможно заменить все знаки вопроса на строчные латинские буквы так, чтобы в строчке было хотя бы k различных букв, выведите «-1» (без кавычек). Иначе выведите любой из способов замены, максимизирующих качество расписания занятий, задаваемого полученной строчкой.

Примеры

исходные данныерезультат
??
1
za
??
3
-1
aza
1
aza
aza
3
-1

Замечания

В первом примере декан может сделать любое расписание из двух пар (даже одинаковых). Но качество расписания «za» равно 26 − 1 = 25, и это самый качественный вариант.
Во втором примере нельзя составить расписание из двух пар с тремя различными предметами.
В третьем примере у декана нет свободы выбора. И хоть расписание получилось плохим (1 − 26 + 1 = −24), ничего лучше предложить нельзя.
В четвёртом примере единственный возможный вариант не содержит трёх различных предметов.
Автор задачи: Алексей Данилюк
Источник задачи: Уральская региональная командная олимпиада по программированию 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2026. Декан и расписание