На предприятии работают несколько сотрудников, зарплата каждого составляет целое число тугриков (разные сотрудники могут иметь разную зарплату). инкассаторы на предприятие 150 монет по 1 тугрику, 150 монет по 2 тугрика, …, 150 монет по 2017 тугриков. деньги — это в точности суммарная зарплата всех сотрудников. при каком наибольшем количестве сотрудников зарплату заведомо удастся раздать (так, что каждый получит в точности причитающуюся ему сумму)?
171
194
Ответы на вопрос:
Если сотрудников 152, то может выйти так, что у 151 сотрудника зарплата 1 тугрик, а у оставшегося - все остальные тугрики. в таком случае зарплату раздать не выйдет, так как есть только 150 монет по 1 тугрику. пусть сотрудников 151 или меньше. упорядочим их по убыванию оставшегося размера выплаты. будем распределять монеты так: заплатим первому в очереди 1 монетой максимального номинала из имеющихся, а затем поставим его в очередь согласно оставшемуся размеру выплаты. почему это сработает: если максимальный номинал монеты x > = 3, то осталось выплатить не меньше, чем 150*(1+2+3++(x-1))+x = 75x^2-74x, у первого в очереди остаток к выплате не меньше, чем (75x^2-74x)/151 > = x. если x = 2, то тех, кому осталось выплатить не больше 1 тугрика, не больше 150 (иначе вся сумма к оплате не больше 150, но если есть хотя бы одна монета в 2 тугрика, то сумма к оплате не меньше 152), значит, первому в очереди можно отдать 2 тугрика. если x = 1, то очевидно, что дать сумму получится.
Популярно: Математика
-
юля271316.01.2022 16:18
-
PeaceMaker133716.08.2020 17:52
-
RazzyMatem30.12.2022 19:26
-
Вигуська26.05.2020 21:37
-
Vladrus2006XD07.01.2023 07:48
-
FiXMy11.01.2021 09:20
-
yrarissikhin08.10.2021 20:01
-
Viking01234509.07.2022 07:17
-
Никола1111111127.02.2022 15:55
-
AnToNoVa1309.03.2021 06:55