Задача А. Ролевая игра
Первоисточник: Всероссийская олимпиада школьников по информатике 2010/2011 учебного года. Региональный этап, первый тур, 21 января 2011 г.
URL первоисточника: http://neerc.ifmo.ru/school/archive/2010-2011/ru-olymp-regional-2011-archive.rar
Задачу добавил: alef
Успешно сдано решений: 15
Ограничение по времени: 4 с
Ограничение по памяти 256 Мб
Вася готовит инвентарь для ролевой игры. В игре должны принять участие n игроков, каждый из которых будет изображать персонажа фантастического мира. В процессе игры каждый персонаж будет обладать некоторым уровнем x, который представляет собой целое число от 1 до m.
Для обозначения уровня планируется использовать специальные значки
двух цветов. Белый значок обозначает один уровень, а красный значок — k уровней. Игрок, изображающий персонажа с уровнем x, должен иметь a белых
значков и b красных
значков, чтобы сумма (a + bk) была равна x. При этом персонажу не разрешается
иметь более чем
(k – 1) белых значков.
Значки для игры готовятся заранее, однако уровни персонажей заранее неизвестны. Для успешного проведения игры всем персонажам необходимо выдать соответствующее их уровням количество значков. Возникает вопрос: какое минимальное суммарное количество значков необходимо подготовить для успешного проведения игры при любых уровнях участвующих персонажей.
Требуется написать программу, которая по заданным числам n, m и k вычисляет минимальное количество значков, которое необходимо подготовить для успешного проведения игры.
Формат входного файла input.txt
Входной файл содержит расположенные в одной строке три целых числа: n, m и k (1 ≤ n ≤ 104, 1 ≤ m ≤ 105, 1 ≤ k ≤ 105).
Формат выходного файла output.txt
В выходном файле должно содержаться одно целое число — минимальное количество значков, которое требуется подготовить
Пример входного файла:
3 4 2
Пример выходного файла:
9
Пояснение к примеру:
В приведенном примере необходимо подготовить 6 красных и 3 белых значка.