Perfect Encoding
Contest: Codeforces Round 485 (Div. 1)
Difficulty rating: 3100
Tags: fft, math

You are working as an analyst in a company working on a new system for big data storage. This system will store $$$n$$$ different objects. Each object should have a unique ID.

To create the system, you choose the parameters of the system — integers $$$m \ge 1$$$ and $$$b_{1}, b_{2}, \ldots, b_{m}$$$. With these parameters an ID of some object in the system is an array of integers $$$[a_{1}, a_{2}, \ldots, a_{m}]$$$ where $$$1 \le a_{i} \le b_{i}$$$ holds for every $$$1 \le i \le m$$$.

Developers say that production costs are proportional to $$$\sum_{i=1}^{m} b_{i}$$$. You are asked to choose parameters $$$m$$$ and $$$b_{i}$$$ so that the system will be able to assign unique IDs to $$$n$$$ different objects and production costs are minimized. Note that you don't have to use all available IDs.

Input format:
In the only line of input there is one positive integer $$$n$$$. The length of the decimal representation of $$$n$$$ is no greater than $$$1.5 \cdot 10^{6}$$$. The integer does not contain leading zeros.

Output format:
Print one number — minimal value of $$$\sum_{i=1}^{m} b_{i}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
36

Example output:
10

Example input:
37

Example output:
11

Editorial:
The problem asks to find integers $$$b_i$$$ such that $$$\prod b_i \ge n$$$ and $$$\sum b_i$$$ is minimized.
Let's suppose that in optimal solution there is $$$x \ge 4$$$ among $$$b_i$$$. It is better to split it to $$$2$$$ and $$$(x-2)$$$: the sum remains the same and the product is increased (or stays the same). So we will use only $$$2$$$ and $$$3$$$ as our $$$b_i$$$. If there are at least three $$$2$$$ among $$$b_i$$$, we can replace them with two $$$3$$$: the sum remains the same, the product is increased.
So, optimal solution looks like this: zero, one or two $$$2$$$s and some $$$3$$$s.
For now let's say that we try all three possibilities for the number of $$$2$$$s. The problem now looks like "find $$$\left\lceil \log_{3} n \right\rceil$$$".
The trick here is that we can estimate the answer very accurately. Let's say that the length of decimal form of $$$n$$$ is $$$L$$$. Then $$$\log_{3} n$$$ is very close to $$$L \frac{\log 10}{\log 3}$$$, the difference is not greater than $$$3$$$. So it is easy to calculate the number $$$p$$$ such that $$$3^p < n / 4 < n < 3^{p+6}$$$.
If we will calculate $$$3^p$$$, then we should adjust this a little bit by multiplying by $$$3$$$ a few number of times. Multiplying by $$$3$$$ can be done in linear time, comparing two numbers also in linear time. Let's now remember that we have tried all the possibilities for the number of $$$2$$$s. We will do it not beforehand, but only now, because now each option can be checked in linear time.
To calculate $$$3^p$$$ we will use binary exponentiation with FFT. If the length of the result is $$$L$$$, then the running time will be $$$O(L \log L + \frac{L}{2} \log L + \frac{L}{4} \log L + \ldots) = O(L \log L)$$$.
To reduce the running time you should store the numbers in base $$$1000$$$, not in base $$$10$$$. This will reduce the length of the number $$$3$$$ times, and the numbers we are getting in FFT will be at most $$$5 \cdot 10^{11}$$$ which is good enough to avoid precision issues.
In the end, running time is roughly equivalent to 4 FFT calls of size $$$2^{19}$$$ which is not that big.
Total complexity — $$$O(L \log L)$$$.