Hints: https://atcoder.jp/contests/agc066/editorial/9708

---

It suffices to solve the case \(N=50\).

[1] Observation

The sequence \(\bigl(d(2^ix)\mid 0\leq i\leq 50\bigr)\) tends to increase for many \(x\).

As the number of digits in \(2^ix\) increases, the sum of the digits seems to increase roughly in proportion to the number of digits.

---

[2] Utilizing multiples of \(5^{50}\)

Let us try setting \(x=5^{50}n\) for some suitable \(n\). In this case, \(2^ix\) is a multiple of \(10^i\) for \(0\leq i\leq 50\), and we can make the following transformation: \(d(2^ix) = d(10^i\cdot 5^{50-i}n) = d(5^{50-i}n)\). Similar to [1], for many \(n\), \(d(2^ix)=d(5^{50-i}n)\) seems to have a decreasing trend according to the number of digits in \(5^{50-i}n\).

---

[3] Utilizing averaging

Let us consider the sequence plotted in [2] as one with a certain decreasing sequence (expected value) with random noise added. Then, if we take many such sequences and average them, the influence of the noise will be very small, making the result close to a decreasing sequence (this is the idea of the (Weak) Law of Large Numbers in statistics). (However, the writer has not made an accurate evaluation of the expected value or variance of \(d(2^ix)\) for \(x=5^{50}n\).)

From this, the following solution can be conceived:

For some \(n_1, \ldots, n_k\), let \(x\) be the integer formed by concatenating \(x_j=5^{50}n_j\).

In this case, \(d(2^ix) = \sum_j d(2^ix_j)\) for \(0\leq i\leq 50\), so if \(k\) is sufficiently large, it seems possible to obtain a decreasing sequence as an average of \(d(2^ix_j)\).

---

[4] Solution

Based on the above, the following solutions can be considered:

• Choose \(n_1, \ldots, n_k\) at random, and let \(x\) be the number formed by concatenating \(5^{50}n_i\). For example, if you set \(k\) to about \(100\) to \(200\) and repeat random selection until you succeed, you can quickly find a solution. You can choose \(n_i\) to be odd so that it is more likely that \(d(2^{49}x) > d(2^{50}x)\) holds, making the success rate even higher. Instead of random selection, you may also simply set \(n_i = i\), etc.
• You may also use the number formed by concatenating \(5^{50}, 5^{51}, \ldots\) as a solution. For example, concatenating \(5^{50}, \ldots, 5^{65}\) yields a solution with \(651\) digits. This solution can be conceived not only from the idea of averaging the decreasing trend but also from eliminating noise through moving averages.