Pregunta Algoritmo del asiento del inodoro


Tomemos una casa normal con un hombre, que tiene que ir al baño cada n minutos, que requieren que el asiento esté levantado, y una mujer, que tiene que hacerlo cada m minutos, lo que requiere un asiento para estar abajo. ¿Existe la posibilidad de crear un O(1) Algoritmo que generará el número exacto de movimientos del asiento del inodoro durante un período determinado de X ¿minutos? Hay dos entradas adicionales diferentes:
1. El hombre siempre deja el asiento después de una visita.
2. El hombre siempre deja el asiento después de una visita.

Conclusión: en la vida real (que involucra n siendo mucho más que m, con X-> infinito), está demostrado que no hay diferencia en varios movimientos de asiento.
 Pero si un hombre lo hace con más frecuencia, entonces una mujer, prolongará la vida del asiento si deja el asiento, pero en este caso uno de ellos (o ambos) probablemente debería ver a un médico.
Ahora sé qué es lo mejor para el asiento en sí, pero qué persona hace más movimientos, es otra pregunta (que no debe hacerse de todos modos).


32
2018-01-22 00:20


origen


Respuestas:


por 2, la respuesta es 2*floor(X/n). El hombre siempre irá al baño con el asiento del inodoro y lo dejará. La mujer nunca lo bajará, ya que solo está activo cuando el hombre va al baño.

1 es un poco más complicado

EDITAR: Duh. por 1, la respuesta es 2*floor(X/m). El asiento del inodoro solo cambia cuando la mujer va al baño.

EDIT2: más o menos el estado inicial del inodoro.

EDIT3: Mi respuesta a 1 solo es correcta si m>=n. Descubriré el resto más tarde.

EDIT4: Si n>=2m, Entonces es 2*floor(X/n), ya que el asiento solo hará la transición cuando el hombre haga pis. Si n>m, Creo que la respuesta también 2*floor(X/n), pero necesito resolver los cálculos.

EDIT5: Entonces, para 2m>n>m, el asiento cambia cuando el hombre orina sobre la mujer y viceversa. La secuencia de visitas hombre / mujer repite cada least_common_multiple(m, n) minutos, entonces solo tenemos que preocuparnos por lo que sucede en ese período de tiempo. La única vez que el asiento sería no la transición cuando el hombre la usa sería si lograra visitarla dos veces seguidas. Dado que la mujer está visitando Más a menudo que el hombre, entre cada visita de hombre hay al menos una visita de mujer. (Dos veces al principio o al final)

La respuesta 1 se convierte en: (n>m ? 2*floor(X/n) : 2*floor(X/m)) + (remainder(X/n) > remainder(X/m) ? 1 : 0). O algo así.


7
2018-01-22 02:26



Sí, hay un algoritmo básico O (1).

Comienzo asumiendo que ambas personas comienzan a "marcar" en t = 0. Creo que la solución debe generalizarse a diferentes tiempos de inicio, pero no es difícil extender desde un "extremo libre" de la línea de tiempo a dos extremos.

Suponer n <= m.

Entonces nuestra línea de tiempo se ve así (una 'x' marca un 'movimiento', no una visita)

  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?

Entonces, la mujer va al piso (t / m) veces, y entre cada vez que la mujer entra, en el intervalo medio abierto (a*m,*m+m] -  el hombre va al menos una vez, volteando el asiento una vez. para cada vez que ella voltea el asiento en un intervalo, también lo voltea una vez. Sin embargo, él posiblemente irá una vez más después su último viaje, dependiendo de sus tiempos relativos, que puede calcular en función de t modulo sus respectivos periodos.

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

Ahora para el caso n> m.

Los roles de la mujer y el hombre se invierten ... el intervalo medio abierto [an / An+n) siempre implicará dos movimientos. El resto de la línea es [t-t% n, t), en la que el hombre va una vez al principio, (que es +1 movimiento, pero contamos +2 para los movimientos de ambas personas en t = 0, que probablemente deberíamos descartar) y la mujer se va si le queda igual o menos tiempo que el que tiene

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

14
2018-01-21 23:14



Sí, lo hay, al menos cuando la implementación puede suponer que el ciclo para un hombre y una mujer se conoce de antemano y que no cambia:

Comience con el mínimo común múltiplo de los tiempos del ciclo hombre / mujer (lcm) Precalcular los movimientos para este período de tiempo (lcm_movements) Ahora solo tienes que lidiar con tu aporte time módulo lcm. Para esto, puede simplemente configurar una tabla de longitud fija que contenga la cantidad de movimientos por cada minuto.

Dado que time y lcm son enteros en Java / C / C ++ / C #, el cálculo real podría ser este:

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

4
2018-01-25 10:30



Suposiciones

  • comenzamos en t = 0 con el asiento del inodoro hacia abajo
  • si el hombre y la mujer llegan al mismo tiempo, entonces las damas primero.

Let lastLadyTime: = floor (X / m) * m y lastManTime: = floor (X / n) * n. Representan la última vez del uso del baño. La expresión (lastLadyTime> lastManTime) es la misma que (X% m <X% n) porque, por definición, X% m = X - lastLadyTime y X% n = X - lastManTime.

Caso: el hombre deja el asiento hacia abajo
La dama nunca tiene que mover el asiento, pero siempre necesita levantarlo. Por lo tanto floor(X/n).

Caso: el hombre deja el asiento hacia arriba, n == m
Él siempre tendrá que levantarlo y ella siempre tendrá que empujarlo hacia abajo excepto en el primer uso del baño cuando no tenga que hacer nada. Por lo tanto 2*floor(X/n) - (X < n ? 0 : 1)

Caso: hombre deja asiento, n> m
Cada vez que lo usa, necesita levantarlo. Ella solo tiene que empujar hacia abajo una vez después de usarlo. Esto sucede todo el tiempo, excepto al final si se acaba el tiempo antes de que ella pueda usar el baño después de él. Por lo tanto, debemos menos 1 si lastManTime> = lastLadyTime (recuerde, señoras primero). Por lo tanto 2 * piso (X / n) - (lastManTime> = lastLadyTime? 1: 0) = 2*floor(X/n) - (X%n <= X%m ? 1 : 0)

Caso: hombre deja asiento, n <m
Similar a n> m. Cada vez que lo usa, necesita empujarlo hacia abajo. Solo necesita levantarlo una vez que lo use. Esto sucede todo el tiempo, excepto al final si se acaba el tiempo antes de que él tenga que ir al baño después de ella. Por lo tanto, debemos menos 1 si lastManTime <lastLadyTime. También una diferencia es que necesita levantar el asiento la primera vez. Por lo tanto, 2 * piso (X / m) - (lastManTime <lastLadyTime? 1: 0) + (X <n? 0: 1) = 2*floor(X/m) - (X%n > X%m ? 1 : 0) + (X < n ? 0 : 1)


2
2018-01-21 23:19



Si todas las variables de minutos son números enteros, entonces podría hacerlo así:

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;

0