Тим ужасно любит
содовую воду, иногда он ею никак не может напиться. Еще более досадным является
тот факт, что у него постоянно нет денег. Поэтому единственным легальным
способом их получения является продажа пустых бутылок из-под соды. Иногда в
добавок к его лично выпитым бутылкам добавляются те, которые Тим иногда находит
на улице. Однажды Тима настолько замучила жажда, что он решил пить до тех пор,
пока мог себе это позволить.
Вход. Три целых неотрицательных числа e, f, c,
где e (e < 1000) – количество пустых бутылок, имеющихся у Тима
в начале дня, f (f <
1000) – количество пустых бутылок, найденных в течение дня, и c (1 < c
< 2000) – количество пустых бутылок, необходимых для покупки новой бутылки.
Выход. Сколько бутылок
содовой воды смог выпить Тим, когда его замучила жажда?
|
Пример
входа |
Пример
выхода |
|
9 0 3 |
4 |
циклы
Анализ алгоритма
Можно считать,
что изначально у Тима имеется e + f пустых бутылок. Моделируем
процесс покупки новых бутылок за имеющиеся в наличии пустые. Содовую воду из
новых бутылок выпиваем, увеличивая таким образом число пустых бутылок. Процесс
продолжаем пока пустых бутылок у Тима хватит хотя бы на одну новую.
Задачу можно решить и без использования циклов. Если
изначально количество пустых бутылок e + f равно 0, то ответ 0.
Если c – количество пустых бутылок, необходимых для покупки новой
бутылки, то стоимость самой содовой воды, находящейся внутри одной бутылки,
составляет c – 1 пустых бутылок.
Сначала у Тима имеется e + f пустых бутылок, в конце у него
должно остаться не менее одной пустой бутылки. То есть за e + f –
1 пустых бутылок Тим может выпить (e + f
– 1) / (c – 1) бутылок содовой
воды.
Реализация алгоритма
Читаем входные
данные.
scanf("%d %d %d",&e,&f,&c);
Изначально количество пустых бутылок empty
равно e + f, а выпитых full равно 0.
empty = e + f;
full = 0;
Пока количество пустых бутылок empty
не меньше c (количества пустых бутылок,
необходимых для покупки новой), покупаем empty / c новых бутылок и выпиваем их.
while (empty >= c)
{
full += empty / c;
empty = empty % c + empty / c;
}
Выводим количество выпитых бутылок full.
printf("%d\n",full);
Второе решение. Рассмотрим вариант, когда Тим будет
совершать обмен по одной бутылке. То есть если у него имеется хотя бы c пустых бутылок, он идет и меняет их на одну полную. Затем
выпивает ее, после чего общее количество пустых бутылок у него уменьшается на c – 1.
scanf("%d %d %d",&e,&f,&c);
empty = e + f;
full = 0;
while (empty >= c)
{
full++;
empty = empty - c + 1;
}
printf("%d\n",full);
Третье решение. Без использования циклов.
scanf("%d %d %d",&e,&f,&c);
if (f + e == 0) res = 0;
else res = (e + f - 1) / (c - 1);
printf("%d\n",res);