[1] Upper digits and lower digits

Let \(R_i\) denote the bottom \(9\) digits of \(X_i\), and \(L_i\) denote the higher digits. That is,

\[ L_i = \lfloor X_i / 10^9 \rfloor,\qquad R_i = X_i \bmod 10^9. \]

Roughly speaking, we can observe the following:

• \(R_i\) is determined only by the most recent \(9\) choices, so there are at most \(2^9\) possibilities.
• \(L_i\) barely changes in subsequent computations.

“Barely changes” means that the decimal representation shifts upward as-is. However, it is possible that a carry from the lower digits may cause the upper digits to change from \(L_i\) to \(L_i+1\) in the future.

[2] Definition of the DP table

Based on the above, we consider the following DP table definition.

At the point when each \(X_i\) has been determined, define the following \(2^9\times 2\) values:

\[ \mathrm{dp}[s][x]\qquad (0\leq s < 2^9, 0\leq x \leq 1). \]

Here, \(s\) represents the most recent \(9\) choices (whether \(A_i\) or \(B_i\) was chosen). Then \(\mathrm{dp}[s][x]\) represents, when the upper digits of \(X_i\) are \(L_i\),

• the minimum possible digit sum of \(L_i+x\).

Once the DP table is defined, we simply write out the transition equations carefully according to the definition. Reading the answer from the DP table is also straightforward.

Almost equivalently, one may define the value \(\mathrm{dp}[R_i][x]\) with the lower digits \(R_i\) similarly. In this case, one would use a hash map or similar structure in the implementation, making execution slower but still fast enough to pass.