Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Субботник

(Время: 1 сек. Память: 16 Мб Сложность: 44%)

В этом году Иван Иванович решил отметить приход осени субботником, чтобы убрать весь мусор во дворе дома номер 31 по улице Осенней. На субботник он пригласил N знакомых старушек, живущих в том же самом доме. Однако, в самом начале мероприятия выяснилось, что по одиночке старушки работают плохо, так как им хочется во время работы еще и поговорить друг с другом.

Иван Иванович подумал и принял волевое решение разбить старушек на группы так, чтобы в каждой группе было не менее 2 старушек. Старушки отличаются друг от друга уровнем разговорчивости, и если в одну группу попадут две старушки, у одной из которых маленький уровень разговорчивости, а у второй - большой, то они не могут поговорить друг с другом и работа будет стопориться.

Назовем разговорчивостью группы разность между максимальным и минимальным уровнями разговорчивости старушек в группе. Например, если уровни разговорчивости старушек в группе равны 7, 3 и 11, то разговорчивость группы равна 11 - 3 = 8. Разговорчивостью разбиения старушек на группы назовем максимальную из разговорчивостей групп, входящих в разбиение.

Требуется написать программу, которая поможет Ивану Ивановичу найти разбиение старушек на группы, разговорчивость которого минимальна.

Входные данные

Входной файл INPUT.TXT содержит в первой строке число N (2 ≤ N ≤ 1000) – количество старушек. Во второй строке записано N чисел от 1 до 109 – разговорчивости старушек.

Выходные данные

Выходной текстовый файл OUTPUT.TXT должен содержать одно целое число, равное минимально возможной разговорчивости разбиения старушек на группы.

Примеры

INPUT.TXTOUTPUT.TXT
12
1 1000000000
999999999
23
1 2 3
2
38
1 10 100 1000 1000 100 10 1
0
410
258 740 156 244 458 680 390 694 844 817
102

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ