Problem AF
Teacher Evaluation

In the city of Capitalistan, all education is performed at private school in which parents pay for their students to go to a certain school. Generally, parents base their choice of school on a variety of factors, such as closeness to the home, class size, teaching style and of course, standardized test results. Every year, all the students in Capitalistan take a standardized test, reciving an integer score between $0$ and $100$.

Sigmund is the teacher of a small urban school, with only capacity for a single class each year. Due to the small class size, the variance of the test results sometimes occasionally make it seem as if his class performed very poorly at the standardized test. Sigmund, who in reality is one of the best teachers in the country, does not like this fact.

Luckily, the standardized tests are graded at the school at which they are written and then reported in to the country’s education authority. This makes it possible for less scrupulous schools to be a bit generous when reporting their results. Since students know what they answered, they would become very suspicious if their results were altered. Similarly, the school can not ignore certain students when reporting results as they are used for assigning grades to the students.

Instead, the school can simply add additional results to raise their average score. Sigmund wants to forge some additional results so that his school increases its average to exactly $P$. Since forging results takes a lot of time, he wants to add as few additional results as possible. How many results need to be added to raise the average score to exactly $P$, given the current results of the students?


The first line of input contains two integers $1 \le N \le 30$ and $0 \le P \le 100$. $N$ is the number of students in Sigmund’s class, and $P$ the average score he wants.

The next line contains $N$ integers between $0$ and $100$. These are the scores Sigmund’s students obtained on the test. It is guaranteed that the average score of his students is strictly less than $P$.


If it is not possible to raise the average to $P$ by adding additional tests, output “impossible”. Otherwise, output the least number of results Sigmund must add to his current set of results to raise the average to exactly $P$.

Sample Input 1 Sample Output 1
4 50
25 30 10 40

Please log in to submit a solution to this problem

Log in