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

Ответ 1

Для 2 ответ 2*floor(X/n). Человек всегда будет ходить в ванную комнату с сиденьем унитаза и опускать его. Женщина никогда не опустит ее, потому что она только когда мужчина идет в ванную.

1 немного сложнее.

EDIT: Дух. Для 1 ответ 2*floor(X/m). Место для туалета переходит только когда женщина идет в ванную.

EDIT2: плюс или минус начальное состояние туалета.

EDIT3: Мой ответ на 1 правильный, если m>=n. Я выясню остальные позже.

EDIT4: Если n>=2m, тогда это 2*floor(X/n), так как место будет переходить только тогда, когда человек будет мочиться. Если n>m, я считаю, что ответ также 2*floor(X/n), но мне нужно выработать математику.

EDIT5: Итак, для 2m>n>m сиденье переходит, когда мужчина идет за женщиной и наоборот. Последовательность посещений мужчин и женщин повторяется каждые least_common_multiple(m, n) минуты, поэтому нам нужно только заботиться о том, что происходит в этот период времени. Единственный раз, когда сидение будет не, когда человек будет использовать его, было бы, если бы ему удалось посетить его дважды подряд. Учитывая, что женщина чаще посещает больше, чем мужчина, между каждым посещением мужчины происходит по крайней мере одно посещение женщины. (Дважды в начале или в конце.)

Ответ 1 затем становится: (n>m ? 2*floor(X/n) : 2*floor(X/m)) + (remainder(X/n) > remainder(X/m) ? 1 : 0). Или что-то в этом роде.

Ответ 2

Да, существует базовый алгоритм 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?

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

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

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

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

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

Ответ 3

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

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

Учитывая, что time и lcm являются целыми числами в Java/C/С++/С#, фактический расчет может быть следующим:

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

Ответ 4

Предположения:

• мы начинаем с t = 0 с сиденьем унитаза вниз
• если мужчина и женщина прибудут в одно и то же время, тогда сначала дамы.

Пусть lastLadyTime: = floor (X/m) * m и lastManTime: = floor (X/n) * n. Они представляют последний раз использование туалета. Выражение (lastLadyTime > lastManTime) совпадает с (X% m < X% n), потому что по определению X% m = X - lastLadyTime и X% n = X - lastManTime.

Дело: человек оставляет место вниз
Леди никогда не должна передвигать сиденье, но ему всегда нужно поднять его. Следовательно, floor(X/n).

Случай: человек оставляет место, n == m
Ему всегда нужно поднять его, и ей всегда нужно будет оттолкнуть его, за исключением самого первого использования туалета, когда ей не нужно ничего делать. Следовательно, 2*floor(X/n) - (X < n ? 0 : 1)

Случай: человек оставляет место, n > m
Каждый раз, когда он его использует, он должен поднять его. Ей нужно только толкать ее, когда он ее использует. Это происходит все время, кроме как в конце, если время истечет, прежде чем она сможет использовать туалет после него. Поэтому мы должны минус 1, если lastManTime >= lastLadyTime (помните, дамы сначала). Следовательно, 2 * пол (X/n) - (lastManTime >= lastLadyTime? 1: 0) = 2*floor(X/n) - (X%n <= X%m ? 1 : 0)

Случай: человек уходит с места, n < м
Аналогично n > m. Каждый раз, когда она ее использует, ей нужно отталкивать ее. Ему нужно только поднять его после того, как она его использует. Это происходит все время, кроме как в конце, если время истекает, прежде чем он должен использовать туалет после нее. Поэтому мы должны минус 1, если lastManTime < lastLadyTime. Также одно отличие заключается в том, что ему нужно снять сиденье в первый раз. Следовательно, 2 * floor (X/m) - (lastManTime < lastLadyTime? 1: 0) + (X < n? 0: 1) = 2*floor(X/m) - (X%n > X%m ? 1 : 0) + (X < n ? 0 : 1)

Ответ 5

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

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;