Субботник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Активисты расчищают берег реки от мусора. Всего на субботник вышло 100 активистов. Им осталось только убрать старые брёвна, принесённые течением.

Одно бревно перетаскивает бригада, в которой может быть два и более человек. Если люди в бригаде имеют разный рост, переносить бревно неудобно. Назовём неудобством бригады разность между ростом самого высокого и самого низкого человека в бригаде. Рост и значение неудобства мы будем измерять в миллиметрах. Назовём неудобством разбиения наибольшее значение неудобства для всех бригад, входящих в разбиение.

Необходимо сформировать бригады таким образом, чтобы неудобство разбиения было минимальным.

Например, пусть в субботнике участвует четыре активиста ростом 1600, 1750, 1650 и 1850 мм и их нужно разбить на две бригады по два человека в каждой. Это можно сделать разными способами. Например, если одну бригаду составить из людей ростом 1600 и 1750 мм, а в другую — из 1650 и 1850 мм, то в первой бригаде неудобство будет 150 мм, а во второй бригаде — 200 мм. Неудобство разбиения в этом случае будет 200 мм. Но если в первую бригаду направить людей ростом 1750 и 1850 мм, а во вторую бригаду — 1600 и 1650 мм, то неудобство разбиения будет равно 100 мм, что лучше.

Вам дан файл, содержащий значения роста 100 активистов, участвующих в субботнике. Вы можете скачать этот файл в разных форматах.

subbotnik.txt — текстовый файл.

subbotnik.xls — электронная таблица Microsoft Excel.

subbotnik.ods — электронная таблица Libre Office Calc.

Ответьте на следующие вопросы. Для ответа на вопросы вы можете использовать программу для работы с электронными таблицами (Microsoft Excel, Libre Office Calc), язык программирования или любые другие средства компьютера.

  1. Пусть все участники субботника объединены в одну бригаду. Чему будет равно неудобство такой бригады?

  2. Пусть активистов нужно разделить на 2 бригады по 50 человек в каждой. Какое будет минимально возможное значение такого разбиения?

  3. Пусть активистов нужно разделить на 10 бригад по 10 человек в каждой. Какое будет минимально возможное неудобство такого разбиения?

  4. Чтобы отнести последнее бревно, требуется бригада из 10 человек. Необходимо выбрать 10 человека из 100 так, чтобы составить бригаду с минимально возможным неудобством. Чему будет равно неудобство этой бригады?