На предприятии работают несколько сотрудников, заработная плата каждого составляет целое число
На предприятии работают несколько служащих, заработная плата каждого сочиняет целое число тугриков (различные сотрудники могут иметь различную зарплату). Инкассаторы привезли на предприятие 150 монет по 1 тугрику, 150 монет по 2 тугрика, , 150 монет по 2017 тугриков. Привезенные средства это в точности суммарная зарплата всех служащих. При каком наибольшем количестве сотрудников заработную плату заранее получится пораздавать (так, что каждый получит в точности причитающуюся ему сумму)?
1 ответ
Олег Мигранян
Если служащих 152, то может выйти так, что у 151 сотрудника заработная плата 1 тугрик, а у оставшегося - все другие тугрики. В таком случае заработную плату пораздавать не выйдет, так как есть только 150 монет по 1 тугрику.
Пусть служащих 151 либо меньше. Упорядочим их по убыванию оставшегося размера выплаты. Будем распределять монеты так:
Оплатим первому в очереди 1 монетой максимального номинала из имеющихся, а потом поставим его в очередь сообразно оставшемуся размеру выплаты.
Почему это сработает: если максимальный номинал монеты x gt;= 3, то осталось выплатить не меньше, чем 150*(1+2+3+...+(x-1))+x = 75x^2-74x, у первого в очереди остаток к выплате не меньше, чем (75x^2-74x)/151 gt;= x.
Если x = 2, то тех, кому осталось выплатить не больше 1 тугрика, не больше 150 (по другому вся сумма к оплате не больше 150, но если есть хотя бы одна монета в 2 тугрика, то сумма к оплате не меньше 152), означает, первому в очереди можно дать 2 тугрика.
Если x = 1, то явно, что дать сумму получится.
Пусть служащих 151 либо меньше. Упорядочим их по убыванию оставшегося размера выплаты. Будем распределять монеты так:
Оплатим первому в очереди 1 монетой максимального номинала из имеющихся, а потом поставим его в очередь сообразно оставшемуся размеру выплаты.
Почему это сработает: если максимальный номинал монеты x gt;= 3, то осталось выплатить не меньше, чем 150*(1+2+3+...+(x-1))+x = 75x^2-74x, у первого в очереди остаток к выплате не меньше, чем (75x^2-74x)/151 gt;= x.
Если x = 2, то тех, кому осталось выплатить не больше 1 тугрика, не больше 150 (по другому вся сумма к оплате не больше 150, но если есть хотя бы одна монета в 2 тугрика, то сумма к оплате не меньше 152), означает, первому в очереди можно дать 2 тугрика.
Если x = 1, то явно, что дать сумму получится.
Гена
Ответ 150*2017= посчитай на калькуляторе, поэтому что каждый получит по 1 монете маловажно какого номинала.
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
Математика, задано на каникулы. ВАРИАНТ 1004
НОМЕР 1,2,3,4,5,6,7,8.
Математика.
Имеются три конденсатора емкостью С1=1мкФ, С2=2мкФ и С3=3мкФ. Какую наименьшую емкость
Физика.
Из точки м выходят 3 луча MP MN и MK причём
Геометрия.
выпиши в свою тетрадь те правила этикета которые тебе не были
Разные вопросы.
Анна хорошо учится у неё много подруг свободное от учёбы время
Обществознание.
10) Килограмм конфет дороже килограмма печенья на 52 р. За 8
Математика.
Во сколько раз число атомов кислорода в земной коре больше числа
Химия.
Составить монолог от имени дневника двоечника 7-10 предложений
Русский язык.
Рассматривая литературный язык как сложное взаимодействие книжного языка и разговорного,В.И.Чернышёв горячо
Разные вопросы.
Арабы входят в __________________ групп народов. Местом расселения арабов с незапамятных
Разные вопросы.
Облако тегов