P2064 The Wonderful Car

You have a wonderful car with an auto-acceleration feature. For example, on day $1$ you can drive a distance of $a$. Then on day $2$, you can increase the distance to one of $2$ to $9$ times that of day $1$ (it must be one of these integers), that is, from $2a$ to $9a$. On day $3$, the distance will be $2$ to $9$ times that of day $2$, and so on. In other words, on day $i$, the distance must be $2$ to $9$ times that of day $i-1$, and it must be an integer multiple of it. You are eager to drive this car from city $A$ to city $B$ for a trip and show off this extraordinary car along the way. You already know the total mileage $S$ you need to travel. Please determine the day $1$ distance and the multiplier used each subsequent day so that the total distance is exactly $S$ and the number of days is minimized. However, because you want to show off your car properly and for safety reasons, you are required to spend at least $2$ days. If no such plan exists, output `-1`.

A positive integer $S$, representing the distance from city $A$ to city $B$.

A single integer representing the minimum number of days required; if there is no solution, output `-1`.

Constraints - For $30\%$ of the testdata, $S \leq 100$. - For $70\%$ of the testdata, $S \leq 10^7$. - For $100\%$ of the testdata, $9 < S \leq 10^8$. Translated by ChatGPT 5