Editorial 1222. Chernobyl’ Eagles

We need to find set of numbers k > 0 and a[i] > 0:
a1 + a2 + ... + ak = n
a1 * a1 * ... * ak -> inf

0. If n = 1 answer = 1, later let's suppose n > 1

1. First of all let's see that in optimal solution a[i] > 1:
Assume a[j] == 1 for some j, also it means that k > 1 (i.e. there is another a[f] in our solution, f != j):
a1 * a2 * ... * a[j-1] * 1 * a[j+1] * ... * ak =
a1 * a2 * ... * a[j-1] * a[j+1] * ... * ak  <
a1 * a2 * ... * a[j-1] * a[j+1] * ... * (ak + 1) =
a1 * a2 * ... * a[j-1] * a[j+1]) * ... * ak + a1 * a2 * ... a[j-1] * a[j+1]) * ... * a[k-1]

It means that such set of number (a1, a2, ..., a[j-1], 1, a[j+1], ..., ak) is not optimal solution

2. Now let's see that in optimal solution a[i] < 4:
Assume a[j] >= 4 for some j, now we can split a[j] to (a[j] - 2) and 2, and find which a[j] will give us better results:

a1 * a2 * ... * a[j] * ... * ak >= a1 * a2 * ... * (a[j] - 2) * 2 * ... * ak
(a[j] - 2) * 2    >= a[j]
2 * a[j] - 4    >= a[j]
a[j] - 4        >= 0
a[j]            >= 4 (as we assumed)

It means that optimal solution will be consist 2's and 3's:
2 * a + 3 * b = n
2 ^ a + 3 ^ b -> max

3. Consider all leftover form of solution which was not proved to be not optimal:

1) 3 * 3 * 3 * 3 * ... (a = 0)
2) 2 * 3 * 3 * 3 * ... (a = 1)
3) 2 * 2 * 3 * 3 * ... (a = 2)
4) 2 * 2 * 2 * 3 * ... (a = 3)
5...) .... a > 3

Solution's 4), 5), 6), ... - is not optimal because we can take any 3 of 2's and replace it with 2 of 3', because
2 * 2 * 2 = 8 < 9 = 3 * 3

It means that 1), 2), 3) potential form of optimal solution

4. Now show that none of the solutions 1), 2), 3) can be compared to each other and it will be mean that 1), 2) and 3) can not be improved, i.e. it is optimal solution.
For this let's look at constraint:
2 * a + 3 * b = n

1) 3 * b1 = n => n % 3 = 0
2) 3 * b2 + 2 = n => n % 3 = 2
3) 3 * b3 + 2 * 2 = 3 * b3 + 4 = 3 * (b3 + 1) + 1 = n => n % 3 = 1

Now we can see that form of optimal solution (1), 2) or 3)) depend on n % 3,
e.g. if n % 3 == 2, then form 2) is optimal solution and nor 1) nor 3) can be formed.