#K78237. Minimum Balls to Win
Minimum Balls to Win
Minimum Balls to Win
You are given an integer n and a list of ball numbers. In this game, you win by drawing a set of balls that, when rearranged, form a sequence of n consecutive integers. Formally, a sequence a1, a2, ..., an is consecutive if it can be reordered so that for the sorted sequence b1, b2, ..., bn the following holds:
$$b_{i} - b_{1} = i - 1 \quad \text{for all } 1 \le i \le n. $$Your task is to determine the minimum number of balls that must be drawn such that the drawn balls can be rearranged into a sequence of consecutive integers. If it is impossible to form such a consecutive sequence with the drawn balls, output impossible
.
Note: The list of ball numbers may contain extra balls beyond the required n balls. However, only the smallest n balls (after sorting) are considered when checking for consecutiveness.
inputFormat
The input is read from standard input and consists of two lines:
- The first line contains a single integer n which is the number of consecutive balls required to win.
- The second line contains a space-separated list of integers representing the ball numbers (the number of balls given can be greater than or equal to n).
It is guaranteed that the list contains at least n numbers.
outputFormat
Print a single line to standard output. If it is possible to select n balls that can be rearranged into a sequence of consecutive integers, output the integer n (i.e. the minimum number of balls drawn). Otherwise, print impossible
.
5
2 4 3 6 1 5
5