马桶座圈算法

Question

让我们带一个普通的房子,一个男人,每n分钟必须上厕所,要求座位上升,女人,每m分钟必须做一次,需要一个座位下来.是否有可能创建一个O(1)算法,在给定的X几分钟内输出准确数量的马桶座圈运动？有两种不同的额外输入:
1.男子在访问后总是离开座位.
这位男士在访问后总是把座位放下.

结论:在现实生活中(涉及n远远超过mX->无穷大),证明了多个座位移动没有区别.
但是,如果一个男人经常这样做,那么一个女人,如果他只是离开座位就会延长座位寿命,但在这种情况下,他们中的一个(或两个)应该去看医生.
现在我知道座椅本身最好的是什么,但是哪个人做出更多动作 - 是另一个问题(不管怎么说都不应该问).

Answer 1

是的,有一个基本的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来计算.

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

现在为n> m的情况.

女人和男人的角色是相反的......半开的间隔 总是涉及两个动作.该行的其余部分是[tt%n,t),其中该男子在开始时进行一次(这是+1移动,但我们在t = 0时对两个人的移动计数+2,我们应该丢弃如果她的时间比他还多或少,那女人就会去[an, an+n)

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

Answer 2

对2,答案是2*floor(X/n).这个男人总是带着马桶座去洗手间,然后把它放下.女人永远不会爱不释手,因为只有当男人去洗手间时才会这样.

1 有点棘手.

编辑:Duh.对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)分钟重复一次,所以我们只需要关注那个时期发生的事情.当男人使用座椅时座椅不会转换的唯一时间是他连续两次访问座椅.鉴于该女子正在访问更多的往往比男人,每个男人的访问之间至少有一个女人的访问.(开头或结尾两次.)

答案1然后变成:(n>m ? 2*floor(X/n) : 2*floor(X/m)) + (remainder(X/n) > remainder(X/m) ? 1 : 0).或类似的东西.

Answer 3

是的，至少当实现可以假设预先知道男人和女人的周期并且它不会改变时：

从男/女周期时间的最小公倍数开始 ( lcm)。预先计算该时间段的变动 ( lcm_movements)。现在您只需处理您的输入timemodulo lcm。为此，您可以简单地设置一个固定长度的表，其中包含每分钟的运动次数。

鉴于Java/C/C++/C# 中time和lcm是整数，实际计算可能是这样的：

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