Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Почтовая служба
Почтовая служба страны со странным названием «Хи в квадрате» решила наконец-то поставить почтовые ящики во всех городах на всей необъятной территории. Но тут же встал вопрос, а как это сделать оптимально? Под оптимальностью руководство почтовой службы понимает минимизацию максимального числа жителей приходящегося в среднем на один почтовый ящик в городе. 

Пусть в стране имеется N городов и B почтовых ящиков. Необходимо распределить почтовые ящики по городам в соответствии с критерием оптимальности, предложенным руководством. 

Рассмотрим пример. Пусть имеется 4 города с населением 120, 2680, 3400 и 200 жителей соответственно. В почтовой службе есть 6 почтовых ящиков. Чтобы оптимально распределить ящики между городами необходимо в первый город отправить 1 ящик, во второй – 2, в третий – 2, в четвертый – 1. Тогда среднее число жителей, приходящихся на один почтовый ящик, в первом городе будет 120, во втором – 1340, в третьем – 1700, в четвертом – 200. Таким образом, максимальное из средних будет 1700. Среди всех возможных вариантов распределения ящиков такой вариант будет наилучшим (т.е. менее чем 1700 жителей на один ящик добиться невозможно). 

Помогите руководству почтовой службы государства «Хи в квадрате» оптимально распределить почтовые ящики по городам и определить, какое максимальное среднее число жителей приходится на один почтовый ящик среди всех городов. Определение этого числа позволит доказать руководству компетентность Вас как специалиста.
Входные данные:
Во входном файле input.txt записаны два натуральных числа N (1 ≤ N ≤ 500000) и B (N ≤ B ≤ 2000000). 
Далее следует N строк, каждая из которых содержит одно натуральное число ai (1 ≤ ai ≤ 5000000) – численность населения в городе i.
Выходные данные:
В выходной файл output.txt требуется вывести единственное число – максимальное среднее число жителей, приходящихся на один почтовый ящик среди всех городов при оптимальном распределении ящиков. Если число получается не целое, то оно должно быть округлено вверх до ближайшего целого числа. Строка единственная.

Примеры:
input.txt output.txt
1 2 7
200000
500000
100000
2 4 6
120
2680
3400
200
1700

Сложность задачи: 25%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 26, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]