Howdy! I have an idea for a problem.
Cody studies in a special school. Teachers there value children's work with integer marks from 1 to 10. Soon the teachers will start to calculate the final mark. Cody is a principled boy, so he wants his final mark to be equal to M. He already looked in the mark-book and he knows that he has N marks and their values. Cody doesn't want to work much so he wants to get as few marks, as possible. Help Cody by telling him how many marks should he recieve and list the exact values.
The final mark is calculated this way: the teacher sums all the marks and divides them with the number of marks. Ex: The final mark of : 1 2 3 4 5 will be 3.
Input: First line contains numbers N and M, the number of marks already in the list and the final mark he wants. The second line containts N integer numbers — the marks in the list.
Output: First line must contain the number X of integer marks he should work at and on the second line you must list them. If the solution doesn't exist — print -1.
Test 1. Input
5 5
1 5 9 7 2
Output
1
6
Test 2. Input
3 8
1 2 3
Output
9
10 10 10 10 10 10 10 10 10
Suggest your ideas of solving and, the most important, suggest the maximum value of N, for the solution to be within 1 and 3 seconds. Almost sure in the test examples, but if you see a mistake — feel free to write about it in the comments. In my opinion, this problem with relatively small N's could be in a Div.2 contest as A or B problem.
Is the final mark rounded down?
Nope, no rounds. If the answer can't be reached — we should output -1.
A solution.
If we can do it with x extra marks, we can also do it with x + 1 extra marks by adding another mark of value M. So we can binary search on X. A value of X is valid iff S + X - N ≤ X·M ≤ S + 10(X - N), where S is the sum of the first N marks.
You should hold on to problems like these -- maybe you can use them in a contest some day.