In this fun little problem you should have a bit of mathematical intuition, and you should trust it.
The easy subtask can be solved in various ways. For example, we can do a simple dynamic programming: for each n, what is the smallest k? In order to solve this problem for a particular n, try all valid choices of ai, each will give you a smaller (i.e., previously solved) subproblem.
(See the published source code for more details.)
Once we examine the correct output for the easy subproblem, we should see that there are only two types of n: if n itself isn’t boring, the answer has k = 1 and a1 = n, otherwise there always was an answer with k = 2.
Could this be true also for larger values of n?
Among the numbers up to 2 ⋅ 109 there is quite a lot of numbers that aren’t boring. If we just limit ourselves to 9-digit numbers, there are 9 × 9!=3 265 920 of those. If we take all pairs of such numbers, we will have about 1013 different pairs, each with a sum between 1 and 2 ⋅ 109. That’s, on average, about 500 pairs per sum.
Now comes the part about trusting your intuition. The non-boring numbers are spread relatively well, so we can expect that the above is what actually happens in practice. From solving the subproblem D1 we also know that this is true for all small values of n.
Hence, we may expect that for the given range of n the answer is always either 1 or 2, and that there are always multiple pairs a1 + a2 that work.
With that in mind, we can write a very simple solution: if n is not boring then output n, otherwise keep trying random a1 until you hit one such that neither a1 nor n − a1 is boring.
Even if we don’t trust our intuition, we have nothing to lose by trying this approach. If it finds a solution, we know that it is optimal. And if it doesn’t, at least we’ll learn some specific values of n that probably need k > 2.
Luckily for us, it turns out to be the case that the above simple solution actually works, and we are done with the task.
While preparing this task we verified that all numbers up to 2 ⋅ 109 have the above property. However, this has to break somewhere – after all, the numbers that are not boring have at most 10 digits. What is the smallest n for which we need k = 3?