## Editorial for ECOO '21 P4 - Chris' Candy

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: AQT, Riolku

The key observation here is how many combinations a given output has. Consider the sample output grouped by type: 2 9 9 9. The counts of the elements look like this:

2 : 1
9 : 3

Now for each element, recall that two sets with the same amount of all elements are the same. Assuming the rest of our elements have combinations, and our last element has total, we have total sets. Why? We can choose to have any number from of our last element, and no matter which we choose, we have combinations for the rest of our elements, for a total of combinations.

Let us have distinct elements, each with counts . Then the total number of combinations is:

We subtract the empty combination here.

As an example suppose we are given , as in the sample input. Then we need:

Well, since we get to choose , what if we just factor ?

And indeed, the sample input has . Another valid output for is 1 2 3, which has .

This should give us the understanding to solve the first subtask. We can simply output of the same integer, since is so small.

For the remaining subtasks, we note that we can find the sum of to be minimal in order to check if it fits under the constraint . In other words, we must find a set of numbers such that

and

is minimum. By making a change of variable of , it follows that

and we are trying to minimize

Now consider that there exists a such that there exist positive integers where . We can try to immediately minimize the sum by replacing with and . In other words, we will replace with and when

The only positive integer solutions to the inequality is when , so it is always better to replace with and . Thus, the optimal solution should have all of not factorable into meaning that all should be prime. So, after factoring into its prime factors, we can compare the sum against .

The second subtask rewards solutions who made these observations but implemented an inefficient solution, potentially by factoring in linear time.

The final subtask can be solved by factoring in time or other efficient methods. Implementation details are left as an exercise to the reader.

Time Complexity: