Problem D
Thanos
Dr. Thanos, data scientist and self-described nihilist,
recently published a paper titled The
snapping point of the universe: why rates of population growth
point towards imminent destruction. In his paper, Thanos
explains that in many planets, the increasing population count
is leading to a diminished quality of life. He is convinced
that his findings will drive sweeping reforms in intergalactic
law, leading to a better life for all organisms.
Thanos turns to you, his confidant, to do some
investigation. He would like some concrete evidence for his
findings to present to the Association of VENGE’s Research
Society. The society, one of the galatic leaders in
egalitarianism and social justice, is holding a special panel
to discuss Thano’s findings. As this involves the chance of
actual legislation being passed, Thanos is convinced that the
panelists are going to be a tough sell. He asks you to
investigate several datasets and see if they could be
potentially helpful in supporting his argument.
Thanos hands you the data for several planets. On each planet’s file, you read that: the planet currently has a population of $P$, its population grows by a factor of $R$ times per year, and its annual food production $F$ in tons. All food produced in a year must be consumed that year; it cannot be saved. Assume that each individual consumes $1$ ton of food per year, and that the population for each planet each year is always counted as a whole number, rounded down. Given this information, your task is to find out the number of years a planet has remaining before its population is no longer sustainable by its food production.
Input
The first line of input consists of a single integer
$T$ ($1 \leq T \leq 2\, 000$), the number
of planets that need to be analyzed.
$T$ lines follow, the
$i$th of which consists of
three space-separated integers $P$ ($1
\leq P \leq 10^9$), $R$ ($1
< R \leq 10^9$), and $F$ ($1
\leq F \leq 10^9$), the metrics of planet $i$ as described above.
Output
Print $T$ lines, the
$i$th of which should
consist of a single integer denoting the number of years the
$i$th planet has before it
is no longer sustainable.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 3 9 2 2 16 5 2 11 |
3 4 2 |
