Problem E
Magic Bucket
Most splash parks require an innovative twist or attraction to beat out the competition, but you’ve got a better way. Magic! You’ve come across a bucket that can duplicate its contents. More specifically, every second, the bucket will multiply its contents by a factor of $s$. You use this to your advantage by adding $r$ litres of water to the bucket each second for $t$ seconds then dumping the contents of the bucket, and repeating. The bucket can only hold a maximum of $m$ litres. If it would overflow when duplicating it will instead cap itself at $m$ litres. The dumping mechanism is also magic and can instantly dump the water but can only be set to do so at whole second intervals. What interval of time $t$ should you wait before dumping the bucket in order to maximize the output rate of water $v/t$ (where $v$ is the volume of water in the bucket at the time of each dump)?
Input
The input consists of a single line containing three integers $s$, $r$, and $m$ ($2 \leq s \leq 100$, $1 \leq r \leq 100$, and $1 \leq m \leq 10^9$) the duplication rate, input rate, and maximum volume of the bucket respectively.
Output
Output a single integer $t$ the smallest whole second time interval to set the dumping mechanism to which will maximize the output rate of water.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 13 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 20 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 3 90 |
4 |
