Cómo resolver el problema SPOJ: VELOCIDAD

Answer 1

Supongamos que la circunferencia de la pista circular es D
La velocidad de A es [matemática] V_a [/ matemática]. El tiempo que toma A para cubrir la distancia D es [matemática] t_a [/ matemática].
La velocidad de B es [matemática] V_b [/ matemática] ‘. El tiempo que toma B para cubrir la distancia D es [matemática] t_b [/ matemática].

Entonces, la velocidad relativa entre ellos es [matemática] V_a – V_b [/ matemática]

Ahora esto es importante. A y B comenzarán desde el punto de partida y después de un cierto tiempo se encontrarán nuevamente en el punto de partida. Este tiempo depende de su velocidad relativa. Será el MCM de sus tiempos individuales, [math] t_a [/ math] y [math] t_b [/ math]. Entonces, en ese momento, tanto A como B estarán exactamente en el punto de partida nuevamente. En este período de tiempo, pueden reunirse en cualquier número de puntos que tengamos que averiguar.
(Nota: después de que se encuentren nuevamente en el punto de partida, el ciclo continúa y continuarán reuniéndose exactamente en los mismos puntos).

Tiempo que ambos tardaron en encontrarse nuevamente en el punto de partida, [matemáticas] T_1 = LCM \ left (t_a, t_b \ right) = LCM \ left (\ frac {D} {V_a}, \ frac {D} {V_b } \ right) [/ math] [math] = \ frac {D} {GCD (V_a, V_b)} [/ math]

Supongamos que se encuentran n veces en el tiempo T1. Entonces, el tiempo entre sus encuentros consecutivos es, [matemática] T_2 = \ left (\ frac {T1} {n} \ right) [/ math]. Este tiempo puede calcularse calculando el tiempo necesario para reunirse por primera vez después de comenzar. [matemática] V_a – V_b [/ matemática] es su velocidad relativa.

Entonces, el tiempo que les tomó reunirse por primera vez, [matemáticas] T_2 = \ left (\ frac {D} {V_a-V_b} \ right) [/ math]

Dividiendo T1 por T2, encontramos n
[matemáticas] n = \ left (\ frac {T_1} {T_2} \ right) = \ left (\ frac {(V_a-V_b)} {GCD (V_a, V_b)} \ right) [/ math]

De ahí la respuesta.

Answer 2

Sí, es cierto que floor [abs (ab) / mcd (abs (a), abs (b))] es la solución donde abs (x) es el valor absoluto de x. Ahora, ¿cómo va eso?

Deje que la persona P1 viaje d1 distancia a la velocidad a y la persona P2 d2 distancia a la velocidad b (debido a sus distintas velocidades). Sea t el tiempo necesario para encontrarse en una posición X. Ahora, P1 cubre la distancia d1 viajando a una velocidad durante t tiempo, y P2 lo hace a la velocidad b durante t tiempo. Verá, t es el factor común, para ser específico, el factor común más alto para el cual d1 / t = a y d2 / t = b. Deje que gcd (abs (a), abs (b)) sea T. Por lo tanto, ahora tenemos el tiempo que les toma encontrarse en cualquier punto arbitrario. Ahora, dado que ab es su velocidad relativa, y la distancia recorrida es proporcional a la velocidad, entonces si C es la longitud de la circunferencia C = (ab) * k donde k es algo constante (en este caso, k es un factor de tiempo). Por lo tanto, cuántas veces se encuentran es en realidad cuántas veces puede entrar T en C, es decir, C / T. Ahora, siendo k el factor tiempo, no afectará el número de puntos de encuentro distintos, asumiendo k como unidad, la solución es (ab) / T o formalmente: floor [abs (ab) / gcd (abs (a), abs (b))]

Answer 3

Cada vez que te golpeen, debes concentrarte e intentar algo u otro para obtener un patrón o una solución en lugar de decepcionarte.
Como en este problema, es un patrón muy simple que debe observar y para eso puede probar algunos casos de prueba usted mismo en spojtoolkit.com para obtener algún patrón visible.
Siempre que te golpeen, puedes hablar con tus colegas y posiblemente puedas obtener ayuda.