Абсолютная игра
Абсолютная игра
Алиса и Боб играют в игру. У Алисы есть массив a из n целых чисел, у Боба есть массив b из n целых чисел. За каждый ход игрок удаляет один элемент своего массива. Игроки ходят по очереди. Алиса ходит первой.
Игра заканчивается, когда оба массива содержат ровно один элемент. Пусть x будет последним элементом массива Алисы, а y — последним элементом массива Боба. Алиса хочет максимизировать абсолютную разницу между x и y, а Боб хочет минимизировать это значение. Оба игрока играют оптимально.
Найдите, какой будет окончательная стоимость игры.
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 1000) - количество значений в каждом массиве.
Вторая строка содержит n целых чисел a1
, a2
, ..., an
(1 ≤ ai
≤ 109
) - числа в массиве Алисы.
Третья строка содержит n целых чисел b1
, b2
, ..., bn
(1 ≤ bi
≤ 109
) - числа в массиве Боба.
Выходные данные
Выведите абсолютную разницу между x и y, если оба игрока играют оптимально.
Пояснение
В первом примере x = 14 и y = 10. Таким образом, разница между этими двумя значениями составляет 4.
Во втором примере размер массивов уже равен 1. Следовательно, x = 14 и y = 42.
4 2 14 7 14 5 10 9 22
4
1 14 42
28