Tim is an obsessive soda drinker, he simply
cannot get enough. Most annoyingly though, he almost never has any money, so
his only obvious legal way to obtain more soda is to take the money he gets
when he recycles empty soda bottles to buy new ones. In addition to the empty
bottles resulting from his own consumption he sometimes finds empty bottles in
the street. One day he was extra thirsty, so he drank sodas until he couldn’t
afford a new one.
Input. Three non-negative integers e, f, c where e (e <
1000) is the number of empty soda bottles in Tim’s
possession at the start of the day, f (f < 1000) is the number of empty soda bottles found during the
day, and c (1 < c < 2000) is
the number of empty bottles required to buy a new soda.
Output. How many sodas did Tim drink on his extra thirsty day?
|
Sample
input |
Sample
output |
|
9 0 3 |
4 |
loops
We can assume
that Tim initially has e + f empty bottles. Let us simulate the
process of purchasing new bottles for existing empty ones. We drink soda water
from new bottles, thus increasing the number of empty bottles. We continue this process until
Tim has enough empty bottles for at least one new.
The problem can be solved without using loops. If the initial
number of empty bottles e + f is 0, then the answer is 0. If c
is the number of empty bottles needed to buy a new bottle, then the cost of the
soda water itself inside one bottle is c
– 1 empty bottles. Initially Tim has e + f empty bottles, and at the end he
must have at least one empty bottle left. That is, for e + f – 1
empty bottles, Tim can drink (e + f – 1) / (c – 1) bottles of soda water.
Algorithm realization
Read the input data.
scanf("%d %d %d",&e,&f,&c);
Initially, the number of empty
bottles empty is equal to e + f, and the number of drunk bottles full is 0.
empty = e + f;
full = 0;
As long as the number of empty
bottles empty is not less than c (the number of empty bottles
needed to buy a new one), we buy empty / c new bottles and drink
them.
while (empty >= c)
{
full += empty / c;
empty = empty % c + empty / c;
}
Print the number of drunk
bottles full.
printf("%d\n",full);
Second solution. Consider the case when Tim
exchanges one bottle at a time. That is, if he has at least c empty bottles, he goes
and exchanges them for a full one. Then he drinks it, after which the total number
of empty bottles he has decreases by 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);
Third solution. No loops used.
scanf("%d %d %d",&e,&f,&c);
if (f + e == 0) res = 0;
else res = (e + f - 1) / (c - 1);
printf("%d\n",res);