We use the following notations in this editorial.

For a positive integer \(X\), let \(f(x)\) be the maximum possible final product when starting with one \(X\) written on the blackboard. - Let \(X_- = \lfloor X/2\rfloor\) and \(X_+ = \lceil X/2\rceil\).

[1] Recurrence relation for \(f(X)\)

We have the following:

• \(f(1) = 1\)
• \(f(X) = \max\{X, f(X_-)f(X_+)\}\) (for \(X\geq 2\))

Actually, the sought value is the greater of the following two.

• When doing zero operations: the final product is \(X\).
• When doing one or more operations: the first operation changes the state of the blackboard to \((X_-, X_+)\). Then, it is optimal to individually handle \(X_-\) and \(X_+\) for the maximum product, after which the final product is \(f(X_-)f(X_+)\).

Additionally, by considering which is larger in \(f(X) = \max\{X, f(X_-)f(X_+)\}\), we can see that the following holds:

• \(f(X) = X\) (for \(X\leq 4\))
• \(f(X) = f(X_-)f(X_+)\) (for \(5\leq X\))

For \(X\leq 4\), this can be seen by actually calculating the values of \(f(X)\) using the reccurrence relation \(f(X) = \max\{X, f(X_-)f(X_+)\}\). For \(5\leq X\), it follows from

\[f(X_-)f(X_+) \geq X_-X_+ \geq \frac{X-1}{2}\cdot \frac{X}{2} = \frac{X-1}{4}\cdot X\geq X\]

that \(f(X_-)f(X_+)\geq X\).

[2] Algorithm and complexity analysis

We use the recurrence relation in [1] to compute the values \(f(X)\) recursively. This can be done efficiently by memoized recursion, reusing the values of \(f(X)\) computed once.

• Sample Code (Python)：https://atcoder.jp/contests/arc135/submissions/29019824
• Sample Code (C++)：https://atcoder.jp/contests/arc135/submissions/29019934

During the computation of \(f(X)\), we have to compute \(f(x)\) for several smaller values of \(x\). Here, only the values that can be represented as \(\lfloor X/2^k\rfloor\) or \(\lceil X/2^k\rceil\) for some \(k\) appear as \(x\). (We can prove in the order \(k = 0, 1, 2, \ldots\) that this is true for the \(k\)-th recursion.)

Thus, if we choose \(K\) so that \(2^{K-1}\leq X < 2^{K}\), there are at most \(2K\) values of \(f(x)\) to compute, allowing us to solve the problem in \(\Theta(\log X)\) time (or \(\Theta(\log X \log\log X)\) time, depending on the method of memoization).