Algorithme du siège de toilette

Question

Prenons une maison ordinaire avec un homme qui doit aller aux toilettes tous les n minutes, ce qui exige que le siège soit relevé, et une femme, qui doit le faire toutes les m minutes, exigeant qu'un siège soit déposé. Existe-t-il une possibilité de créer un O(1) algorithme qui donnera le nombre exact de mouvements du siège des toilettes pour une période donnée de X minutes ? Il existe deux entrées supplémentaires différentes :
1. L'homme laisse toujours le siège relevé après une visite.
2. L'homme pose toujours le siège après une visite.

Conclusion : dans la vie réelle (ce qui implique n étant bien plus que m avec X->infini), il est prouvé qu'il n'y a pas de différence dans un certain nombre de mouvements du siège.
Mais si un homme le fait plus souvent qu'une femme, la durée de vie du siège sera prolongée s'il laisse le siège relevé, mais dans ce cas, l'un des deux (ou les deux) devrait probablement consulter un médecin.
Je sais maintenant ce qui est le mieux pour le siège lui-même, mais quelle personne fait le plus de mouvements - c'est une autre question (qui ne devrait pas être posée de toute façon).

Answer 1

Oui, il existe un algorithme de base O(1).

Je pars du principe que les deux personnes commencent à "faire tic-tac" à t=0. Je pense que la solution devrait se généraliser à différents moments de départ, mais il n'est pas difficile de s'étendre d'une "extrémité libre" de la ligne de temps à deux extrémités.

Supposons que n <= m.

Notre calendrier ressemble alors à ceci (un "x" indique un "déménagement", pas une visite).

  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?

Donc, la femme va plancher(t/m) fois, et entre chaque fois que la femme va -- dans l'intervalle semi-ouvert (a*m,*m+m] -- l'homme y va au moins une fois, retournant ainsi le siège une fois. pour chaque fois qu'elle retourne le siège dans un intervalle, il le retourne également une fois. Cependant, il est possible qu'il y aille une fois de plus après son dernier voyage, en fonction de leurs timings relatifs, que l'on peut calculer en fonction de t modulo leurs périodes respectives.

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

Maintenant, pour le cas n > m.

Les rôles de la femme et de l'homme sont inversés... l'intervalle semi-ouvert [a_n, a_n+n) impliquera toujours deux mouvements. Le reste de la ligne est [t-t%n, t), dans laquelle l'homme fait un coup au début, (ce qui représente +1 coup, mais nous avons compté +2 pour les coups des deux personnes à t=0, ce que nous devrions probablement écarter) et la femme joue si elle a autant ou moins de temps qu'il lui reste

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

Answer 2

Pour 2 la réponse est 2*floor(X/n) . L'homme ira toujours aux toilettes avec le siège des toilettes baissé et le laissera baissé. La femme ne le posera jamais, puisqu'il n'est relevé que lorsque l'homme va aux toilettes.

1 est un peu plus délicat.

EDIT : Duh. Pour 1 la réponse est 2*floor(X/m) . Le siège des toilettes ne transite que lorsque la femme va aux toilettes.

EDIT2 : Plus ou moins l'état initial des toilettes.

EDIT3 : Ma réponse à la question 1 n'est correcte que si m>=n . Je trouverai le reste plus tard.

EDIT4 : Si n>=2m alors c'est 2*floor(X/n) puisque le siège ne fait la transition que lorsque l'homme va faire pipi. Si n>m je crois que la réponse est aussi 2*floor(X/n) mais je dois faire des calculs.

EDIT5 : Donc, pour 2m>n>m le siège change quand l'homme va faire pipi après la femme et vice versa. La séquence de visites homme/femme se répète chaque année. least_common_multiple(m, n) minutes, donc nous ne devons nous préoccuper que de ce qui se passe pendant cette période. Le seul moment où le siège no La transition quand l'homme l'utilise serait s'il réussit à la visiter deux fois de suite. Étant donné que la femme visite plus plus souvent que l'homme, entre chaque visite d'homme il y a au moins une visite de femme. (Deux fois au début ou à la fin.)

La réponse 1 devient alors : (n>m ? 2*floor(X/n) : 2*floor(X/m)) + (remainder(X/n) > remainder(X/m) ? 1 : 0) . Ou quelque chose comme ça.

Answer 3

Oui, il y en a une, du moins lorsque la mise en œuvre peut supposer que le cycle d'un homme et d'une femme est connu à l'avance et qu'il ne change pas :

Commencez par le multiple le moins commun des temps de cycle homme/femme ( lcm ). Précalculez les mouvements pour cette période ( lcm_movements ). Maintenant, vous n'avez plus qu'à vous occuper de votre entrée time modulo lcm . Pour cela, il suffit de créer un tableau de longueur fixe contenant le nombre de mouvements pour chaque minute.

Étant donné que time y lcm sont des entiers en Java/C++/C#, le calcul réel pourrait être le suivant :

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

Answer 4

Hypothèses :

• nous commençons à t=0 avec le siège des toilettes baissé
• si l'homme et la femme arrivent en même temps, alors les dames d'abord.

Soit lastLadyTime := floor(X/m)*m et lastManTime := floor(X/n)*n. Ils représentent le dernier moment d'utilisation des toilettes. L'expression (lastLadyTime > lastManTime) est identique à (X%m < X%n) car, par définition, X%m = X - lastLadyTime et X%n = X - lastManTime.

Cas : un homme laisse son siège baissé
La dame n'a jamais besoin de déplacer le siège, mais lui doit toujours le soulever. D'où floor(X/n) .

Cas : l'homme laisse le siège relevé, n == m
Il devra toujours le soulever et elle devra toujours le pousser vers le bas, sauf lors de la toute première utilisation des toilettes où elle n'a rien à faire. D'où 2*floor(X/n) - (X < n ? 0 : 1)

Cas : l'homme laisse le siège relevé, n > m
Chaque fois qu'il l'utilise, il doit le soulever. Elle doit seulement le pousser vers le bas une fois qu'il l'a utilisé. Cela se produit tout le temps, sauf à la fin si le temps est écoulé avant qu'elle puisse utiliser les toilettes après lui. Nous devons donc retrancher 1 si lastManTime >= lastLadyTime (rappelez-vous, les dames d'abord). Donc 2*floor(X/n) - (lastManTime >= lastLadyTime ? 1 : 0) = 2*floor(X/n) - (X%n <= X%m ? 1 : 0)

Cas : l'homme laisse le siège relevé, n < m
Similaire à n > m. Chaque fois qu'elle l'utilise, elle doit le pousser vers le bas. Il doit seulement le soulever une fois après qu'elle l'ait utilisé. Cela se produit tout le temps, sauf à la fin si le temps s'écoule avant qu'il ne doive utiliser les toilettes après elle. Par conséquent, nous devons retrancher 1 si lastManTime < lastLadyTime. Une autre différence est qu'il doit soulever le siège la première fois. D'où 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)

Answer 5

Si toutes les variables minute sont des entiers, vous pouvez procéder comme suit :

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;