Арифметическая прогрессия
(Время: 2 сек. Память: 32 Мб Сложность: 60%)
К элементам некоторой последовательности A, состоящей из n чисел, были добавлены n элементов другой последовательности B. После чего все элементы новой последовательности были перемешаны. В результате образовалась новая последовательность C, состоящая из 2n элементов.
Требуется восстановить исходную последовательность A из последовательности C. При этом известно, что последовательность A является арифметической прогрессией.
Напомним, что последовательность A1, A2, …, An называют арифметической прогрессией, если Ai = Ai-1 + d для всех i от 2 до n и некоторого d.
Входные данные
В первой строке входного файла INPUT.TXT содержится целое число n (1 ≤ n ≤ 105). В следующей строке находится 2n целых чисел – элементы последовательности C (-109 ≤ Ci ≤ 109).
Гарантируется, что из чисел последовательности C можно выбрать n чисел так, чтобы они образовывали арифметическую прогрессию.
Выходные данные
В выходной файл OUTPUT.TXT выведите два числа A1 и d – первый элемент и разность найденной арифметической прогрессии. Если d = 0, то число A1 должно встречаться среди заданных чисел не менее n раз. Если существует несколько решений, выведите любое.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
16 14 2 10 8 6 | 2 6 |
Пояснение к примеру
Искомой последовательностью может служить последовательность чисел 2, 8, 14 (A1 = 2, d = 6). Также в качестве верного ответа здесь может быть последовательность 2, 6, 10 (A1 = 2, d = 4).
Система оценки
Решения, работающие верно только для n ≤ 100, будут оцениваться в 25 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
