An Average Problem
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 2.0 seconds
Determine whether it is possible to generate a sequence of integers x_1, x_2,\dots,x_N (1 \le x_i \le 1\,000\,000) that meets the following criteria:
- The number of values is N.
- The mean is A (the sum of values divided by the number of values).
- The median is B (the
middle
value if the sequence is sorted – it is guaranteed that N is odd). - The mode is C (the most frequent value). Note that there is only one mode – there should not be any other value that occurs as frequently as the mode.
For 60% of the points, you should also output a valid sequence meeting the above criteria (if one exists).
Input
There will be a single line, containing four space-separated integers: N, the number of elements, A, the mean, B, the median, and C, the mode (1 \le N < 100\,000, 1 \le A,B,C \le 1\,000\,000). It is guaranteed that N is odd.
Output
The first line should contain either Possible
or Impossible
, representing whether it is possible to generate a valid sequence that meets the above criteria or not.
If it is possible to generate a valid sequence, you may also output a second line containing N space-separated integers in any order, representing a sequence that meets the above criteria. Each element of the sequence should be an integer x_i, such that 1 \le x_i \le 1\,000\,000. If there is more than one possible sequence, you may output any of them.
Subtasks
- Subtask 1 (5%): A = B = C
- Subtask 2 (10%): N = 1 \text{ or } 3
- Subtask 3 (20%): B = C
- Subtask 4 (35%): N < 1000
- Subtask 5 (30%): No further restrictions apply.
Scoring
For each test case:
- If you correctly determine that it is possible to generate a sequence, and do not output a sequence, or output an invalid sequence, you will score 40% for that test case.
- If you correctly determine that it is possible to generate a sequence, and also output a valid sequence, you will score 100% for that test case.
- If you correctly determine that it is impossible to generate a sequence, you will score 100% for that test case.
Your score for each subtask will be the minimum score among all test cases in that subtask.
-
Sample Input 1
5 7 6 5
Sample Output 1
Possible 5 5 6 7 12
-
Sample Input 2
3 5 4 6
Sample Output 2
Impossible
-
Sample Input 3
7 8 9 9
Sample Output 3
Possible 6 7 7 9 9 9 9