e-olymp 891. Покупка цветов

Задача. Покупка цветов

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $a$ рублей за штуку и гладиолусы по $b$ рублей за штуку ($a < b$). У Васи есть $c$ рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже $c$ рублей. Помогите ему вычислить стоимость такого букета.

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

Три целых числа $a$, $b$, $c$ ($1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000$).

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

Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.

Тесты

Ввод Вывод
1 5 7 0 0
2 3 5 10 9
3 2 3 11 11
4 48 64 306 304
5 17 20 100 100
6 13 15 260 260
7 29 53 999 986
8 17 28 16 0
7 75 100 1000 1000

Решение

Рассмотрим частный случай. Если можно купить по минимальной цене ромашки так, что у нас не будет остатка, то полученное количество цветов будет максимальным и увеличить их стоимость будет невозможно. Значит ответом будет количество денег в кошельке у Васи.

Далее, что бы найти решение для оставшихся вариантов, необходимо найти наибольшую сумму стоимостей максимального количества цветов не превышающую $c$ рублей. Максимальное количество цветов n будет равно количеству цветов с минимальной стоимостью которое можно купить за имеющиеся у Васи деньги. ($c / a$).

Что бы оптимизировать код будем проверять условия в цикле с обоих концов (меняя местами количество ромашек и гладиолусов), таким образом мы выполним его за в 2 раза меньшее количество проходов и быстрее найдём максимум. А так же при равенстве искомого значения с его максимально возможным остановим проверку.

Код

Условие задачи

Решение

Код на ideone

2 thoughts on “e-olymp 891. Покупка цветов

    • Избавьтесь от экстренного выхода из цикла — делайте все в заголовке цикла.
    • Печать результата лучше сделать один раз и в самом конце.
    • Вы пишите комментарии в коде с большой буквы и с точкой в конце, но в данном случае это не предложения, а пояснение к объявленной переменной.
    • В пояснении Вы говорите о соотношениях величин, а не приводите фрагменты кода. Значит логично все разметить как математические формулы в laTeX, а не code.
    • Остаток от деление выполняется раньше сравнения — скобки в условии можно не ставить.

    Идея с проверкой частного случая и проходом с двух концов действительно приносит экономию по времени ~5%. Но значительно увеличивает код и усложняет его чтение. Если задача была вписаться в имеющиеся ограничения по времени, то у Вас в любом случае запас в 500 раз! В практике программирования это называется преждевременной оптимизацией. Дональд Кнут утверждает, что

    Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

    И я склонен с ним согласиться. С некоторыми оговорками. Хотя, если целью было попасть в таблицу рекордов… Но не попали же?
    Ладно, оставим как есть. Только не делайте этого на соревнованиях по программированию.

  1. Не думаю, что первый условный оператор необходим. Но оставим как есть.
    Вообще-то циклы здесь совсем не нужны. Не знаю, почему все их используют.

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

Добавить комментарий