Задача. Покупка цветов
На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $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 раза меньшее количество проходов и быстрее найдём максимум. А так же при равенстве искомого значения с его максимально возможным остановим проверку.
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> using namespace std; int main() { int a, b, c, max; cin >> a >> b >> c; if (c % a == 0) max = c; else { int n = c / a; // максимальное количество цветков max = 0; for (int i = 0; i <= (n / 2) && max != c; i++) { int first = (n - i) * b + i * a; if (first > max && first <= c) max = first; int second = (n - i) * a + i * b; if (second > max && second <= c) max = second; } } cout << max; return 0; } |
Идея с проверкой частного случая и проходом с двух концов действительно приносит экономию по времени ~5%. Но значительно увеличивает код и усложняет его чтение. Если задача была вписаться в имеющиеся ограничения по времени, то у Вас в любом случае запас в 500 раз! В практике программирования это называется преждевременной оптимизацией. Дональд Кнут утверждает, что
И я склонен с ним согласиться. С некоторыми оговорками. Хотя, если целью было попасть в таблицу рекордов… Но не попали же?
Ладно, оставим как есть. Только не делайте этого на соревнованиях по программированию.
Не думаю, что первый условный оператор необходим. Но оставим как есть.
Вообще-то циклы здесь совсем не нужны. Не знаю, почему все их используют.
Я здесь не упрощал формулу, чтобы яснее было как она получилась.