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

e-olymp 127. Баксы в банке

Задача

Папа Карло подарил Буратино [latex]1[/latex] доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой [latex]N[/latex]-й день рождения в банке будет не менее чем [latex]S[/latex] долларов?

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

Единственное число — значение [latex]S[/latex]. [latex]1 ≤ S ≤ 240[/latex].

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

Искомое значение [latex]N[/latex].

Тесты

# Входные данные Выходные данные
1 1 1
2 98 5
3 99 5
4 100 6
5 549755813888 38

Код

Решение задачи

Для начала найдём формулу, по которому папа Карло дарит, а Буратино — складывает в банку доллары: [latex]x=2\cdot x+k[/latex].
А теперь установим допустимый предел суммы долларов в банке и начальные условия: [latex]s<n[/latex] и [latex]x=1[/latex], [latex]k=1[/latex], [latex]s=1[/latex].

Ссылки

Условие задачи на e-olymp
Код решения на ideone

e-olymp 127. Баксы в банке

Условие

Папа Карло подарил Буратино [latex]1[/latex] доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой [latex]N[/latex]-й день рождения в банке будет не менее чем [latex]S[/latex] долларов?

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

Единственное число — значение [latex]S[/latex]. [latex]1\le S \le 240[/latex].

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

Искомое значение [latex]N[/latex].

Задача взята с сайта e-olymp.

Тесты

Входные данные Выходные данные
15 3
25 4
9 3
99 5
199 6
333 7
56 5
478 8
809 8

Код

Решение

В данной задаче [latex]sum[/latex] — сколько долларов в банке, [latex]p[/latex] — сколько долларов Папа Карло подарил Буратино. Пока [latex]sum<s[/latex] мы увеличиваем [latex]N[/latex] на [latex]1[/latex] и считаем сколько Папа Карло подарит Буратино [latex]p=p\cdot 2+n[/latex] и суммируем его с тем что лежит в банке [latex]sum=sum+p[/latex] или же как у меня что одно и тоже [latex]sum += p[/latex]. После этого выводим [latex]N[/latex].
Код программы
Засчитанное решение