Групу туристів вирішили розмістити в декількох автобусах так, щоб у всіх автобусах була одна й та ж сама кількість туристів. Спочатку до кожного ав-
тобуса посадили по 22 пасажири, але в такому випадку одному з туристів не вистачило місця. Коли з’ясувалось, що один з автобусів несправний, то в ре-
шті автобусів туристи розмістились саме так, як було потрібно. Скільки ту-
ристів було в групі, якщо відомо, що їхня кількість перевищувала 100 осіб?
Решение:
Если сотрудников 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, то первому в очереди надо выплатить не меньше 2 тугриков, поскольку в противном случае сумма всех монет была бы не больше 151 (не более 151 человека, каждому надо выплатить не более 1 тугрика), но сумма всех монет не меньше, чем 150*1 + 2 = 152.
Если x = 1, то очевидно, выплатить получится.