Алгоритм унитаза

Question

Давайте возьмем обычный дом с мужчиной, который должен ходить в туалет каждые n минут, требующий поднятия места, и женщиной, которая должна делать это каждые m минут, требующей места. быть внизу. Есть ли возможность создать алгоритм O(1), который будет выводить точное количество движений сиденья унитаза за данный период X минут? Есть два разных дополнительных входа:
1. Мужчина всегда покидает место после посещения.
2. Мужчина всегда опускает сиденье после посещения.

Вывод: в реальной жизни (которая включает n намного больше, чем m, с X-> бесконечностью), доказано, что нет разницы в количестве движений сидений ,
Но если мужчина делает это чаще, чем женщина, это продлит срок службы сиденья, если он просто оставит сиденье вверх, но в этом случае один из них (или оба), вероятно, должен обратиться к врачу. < бр /> Теперь я знаю, что лучше для самого сиденья, но какой человек делает больше движений - это другой вопрос (который не следует задавать в любом случае).

Answer 1

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

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

Предположим, что n <= m. </h3> Тогда наша временная шкала выглядит следующим образом («х» обозначает «движение», а не посещение) 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.

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

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

Answer 2

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

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

РЕДАКТИРОВАТЬ: Дух. Для 1 ответ - 2*floor(X/m). Сиденье унитаза переключается только тогда, когда женщина идет в ванную.

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

РЕДАКТИРОВАТЬ3: Мой ответ на 1 является правильным, только если m>=n. Остальное я выясню позже.

РЕДАКТИРОВАТЬ4: Если n>=2m, то это 2*floor(X/n), так как место будет переходить только тогда, когда человек мочится. Если n>m, я считаю, что ответ также 2*floor(X/n), но мне нужно разобраться с математикой.

РЕДАКТИРОВАТЬ5: Таким образом, для 2m>n>m сиденье меняется, когда мужчина мочится за женщиной, и наоборот. Последовательность визитов мужчины / женщины повторяется каждые least_common_multiple(m, n) минуты, поэтому нам нужно только задуматься о том, что происходит в этот период времени. Единственное время, когда сиденье будет не переходить, когда человек его использует, будет, если ему удастся посетить его дважды подряд. Учитывая, что женщина навещает на больше * на 1028 * чаще, чем мужчина, между каждым посещением мужчины происходит как минимум одно посещение женщины. (Дважды в начале или в конце.)

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

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

Answer 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;