Hide

Problem D
Two Numbers

/problems/vths21.twonumbers/file/statement/en/img-0001.png
Credit: The Art of Problem Solving (AoPS.com)

During the Covid pandemic, Theta like many other fourth graders nationwide joined AoPS (The Art of Problem Solving), an online website for mathematically interested students.

One of the problems she’s found on the site goes like this: there are $n$ numbers in a list. Two numbers are removed. The average and the median change by a certain amount. Find the numbers that were removed.

Input

The input consists of a single test case. The first line contains an integer $n$ ($3 \le n \le 100\, 000$). The second line contains $n$ distinct integers $b_ i$ ($0 \le b_ i \le 10\, 000\, 000$). The third and last line contains one integer $a$ and a real number $m$ ($-1\, 000 \le a, m \le 1\, 000$), describing the amount by which the average and median changes after two integers are removed. You may assume that the average of the given sequence is an integer.

Output

Output all possible pairs of integers that could be removed from the list such that the average and median changes by $a$ and $m$, respectively. Output each pair on a separate line, sorted by their first number. List the smaller number of each pair first.

Sample Input 1 Sample Output 1
8
9 42 6 30 23 2 1 15
0 -1.5
9 23
Sample Input 2 Sample Output 2
9
24 7 1 42 21 3 22 34 8
-1 -13
21 22
Sample Input 3 Sample Output 3
16
184 106 118 142 160 172 136 124 166 100 130 112 178 148 190 154
0 0.0
100 190
106 184
112 178
118 172
124 166
130 160
136 154
142 148

Please log in to submit a solution to this problem

Log in