PD> взять минимальное из НОК для пар блистеров/флаконов
Если тебя устраивает сложность алгоритма, который рассматривает пары и выбирает ближайший день, то и решай второй случай так же.
Для каждой пары:
1. Находишь НОК и узнаёшь период;
2. Применяешь китайскую теорему об остатках (для случая не-взаимно простых модулей): https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Generalization_to_non-coprime_moduli Либо узнаёшь, что решения для этой пары чисел нет, либо получаешь смещение.
3. Целочисленным делением размера кучи на размер блистера узнаёшь время, через которое размер всех кучек станет не больше размера блистера (раз говоришь, что там может быть произвольное число, тогда начать могли с 100000 штук, даже если потом пополнять будем по 10 или по 15).
Складываешь 1 и 3, вычитаешь 2. В целом, делать можно пункты в любом порядке, как удобнее писать.
Возраст, увы, у меня почтенный, а поэтому приходится ежедневно принимать таблетки.
Таблеток N видов. Принимаю я ровно 1 таблетку каждого вида в день (это действительно так).
Таблетки в блистерах или флаконах. В одних блистерах 10 штук, в других 15, во флаконах иные значения.
Когда блистер или флакон заканчивается, я заменяю его на новый.
И вот сегодня одновременно закончились 2 разных блистера. Не помню, было ли такое когда-то раньше.
Отсюда задача — по исходному набору блистеров/флаконов найти день, когда одновременно закончатся хотя бы 2 блистера/флакона. Разумеется, у меня достаточно новых блистеров/флаконов.
Вариант 1. В день X я начинаю прием, все блистеры/флаконы полные.
Вариант 2. В день X я начинаю прием, но блистеры/флаконы неполные, в каждом осталось свое количество таблеток.
Найти день Y, в который закончатся хотя бы 2 блистера/флакона. Для определенности в течение некоторого срока, скажем, года. Если такого не будет, ответ — нет.
Программистское решение. Оно тривиально для обоих вариантов. Просто в цикле делаем T[i]-- каждому блистеру/флакону и смотрим, не получили ли мы хотя бы два нуля на данной итерации цикла. В общем, точная калька того, что я делаю в реальности.
Математическое решение для варианта 1. Оно тоже простое — нужно взять минимальное из НОК для пар блистеров/флаконов. Если, скажем, в одном блистере 10 таблеток, в другом 15, то НОК == 30, и через 30 дней я полностью съем 3 блистера первого лекарства и 2 — второго.
Существует ли математическое решение для варианта 2 ?
Не надо думать, что вариант 2 получился из варианта 1 спустя сколько-то дней, то есть начал я с полных блистеров/флаконов. Нет. Просто в день X в каждом блистере/флаконе Ti таблеток, а как их количества стали такими — не обсуждается.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Математическое решение для варианта 1. Оно тоже простое — нужно взять минимальное из НОК для пар блистеров/флаконов. Если, скажем, в одном блистере 10 таблеток, в другом 15, то НОК == 30, и через 30 дней я полностью съем 3 блистера первого лекарства и 2 — второго.
PD>Существует ли математическое решение для варианта 2 ?
НОК(a,b) — это такое наименьшее целое число, которое делится и на a и на b с остатком 0.
Я думаю, можно НОК обобщить так, чтобы он делился на a с остатком x и на b с остатком y. И вычисление будет примерно такое же, как для обычного НОК.
