Алгоритм сиденья унитаза

Если все минутные переменные являются целыми числами, то вы могли бы сделать это так:

int toilet_seat_movements = 0;
bool seat_up = false;

for (i = 0; i <= total_minutes; i++)
{
    if (seat_up)
    {
        if (i % woman_minutes == 0)
            toilet_seat_movements++;
    }
    else
    {
        if (i % man_minutes == 0)
            toilet_seat_movements++;
    }
}

return toilet_seat_movements;

Да, есть базовый алгоритм O(1).

Я начинаю с предположения, что оба человека начинают "тикать" при t=0. Я считаю, что решение должно быть обобщено на разные стартовые времена, но нетрудно перейти от одного "свободного конца" временной шкалы к двум концам.

Предположим, что n <= m.

Тогда наша временная шкала выглядит так ("x" обозначает "движение", а не визит)

  0     m    2m    ..              t-t%m  t
  +-----+-----+-----+-----+-----+-----+--o
W x     x     x     x     x     x     x 
M x  x    x    x       x     x    x     x?

Итак, женщина идет по времени этажа(t/m) и между каждый раз, когда женщина уходит -- в полуоткрытом интервале (a*m,*m+m] -- человек ходит хотя бы один раз, таким образом перевернув сиденье один раз. за то. каждый раз, когда она переворачивает сиденье за промежуток времени, он также переворачивает его один раз. Тем не менее, он, возможно, пойдет еще раз после того, как ее последняя поездка, в зависимости от их относительного времени, которые вы можете рассчитать на основе t modulo их соответствующих периодов.

total_moves = floor(t/m) * 2 + (t%m < t%n ? 1 : 0)

Теперь в случае n > m.

Роли женщины и мужчины меняются на противоположные... полуоткрытый интервал. [an, an+n) всегда будет два хода. Остальное линии [t-t-t%n, t), в которой человек идет один раз в начале, (что означает +1 ход, но мы посчитали +2 для обоих ходов при t=0, который мы, вероятно, должны отбросить), и женщина идет, если у нее осталось равное или меньшее время, чем у него

total_moves = floor(t/n) * 2 - 1 + (t%m >= t%n ? 1 : 0)

Да, по крайней мере, когда реализация может предположить, что цикл для человека и женщины известен заранее, и что он не изменяется:

Начните с наименее распространенных Несколько времен цикла человека / женщины ( LCM ). Закалить движения в течение этого периода времени ( lcm_movements ). Теперь вам нужно только иметь дело с вашим входом Modulo LCM . Для этого вы можете просто настроить таблицу фиксированной длины, содержащую количество движений на каждую минуту.

Учитывая время время и LCM целых чисел в Java / C / C ++ / C # Фактический расчет может быть это:

return ( time / lcm ) * lcm_movements + movements[ time % lcm ];

Допущения:

• Начнем с T = 0 с сиденьем унитаза вниз
• Если человек и женщина приезжают в то же время, то дамы первыми.

Пусть lastladytime: = пол (x / m) * m и lastmantime: = пол (x / n) * n. Они представляют собой последнее время использования туалета. Выражение (lastladytime> lastmantime) такое же, как (x% m

Дело: Человек оставляет сиденье
Дама никогда не должна двигать сиденье, но ему всегда нужно поднимать его. Следовательно, пол (X / N) .

Человек: Человек оставляет сиденье вверх, n == m
, ему всегда нужно будет поднять его, и ей всегда нужно будет толкать его, кроме как в самом первом использовании туалета, когда у нее нет делать что-либо. Следовательно 2 * Этаж (X / N) - (x