Considere dos automóviles A y B que corren infinitamente (ya sea en sentido horario o antihorario) en una carretera circular. Dada la velocidad de los autos a y b . Si a o b es positivo, indica que se están moviendo en el sentido de las agujas del reloj, de lo contrario, se están moviendo en el sentido contrario a las agujas del reloj. La tarea es encontrar el número de puntos distintos en los que se encontrarán.
Ejemplos:
Input : a = 1, b = -1 Output : 2 Explanation Car A is moving clockwise while Car B is moving anti-clockwise but their speeds are same, so they will meet at two points i.e at the starting point and diametrically corresponding opposite point on the road. Input : a = 1, b = 2 Output : 1
Requisitos previos : GCD | MCM
Aproximación :
Sea d la circunferencia de la carretera circular . Sea t a y t b respectivamente
el tiempo que tardan los coches A y B. Su velocidad relativa es a – b . A y B comienzan desde el punto de partida y después de un tiempo, se encontrarán en el punto de partida nuevamente. Este tiempo puede ser calculado por el MCM de t a y t b
. Dentro de este período de tiempo, pueden encontrarse en ciertos puntos que necesitan ser descubiertos. Observe que, después de encontrarse en el punto de partida, continúan encontrándose en el mismo punto.
El tiempo necesario para volver a encontrarnos en el punto de partida será,
T1 = LCM(ta, tb) = LCM(d/a, d/b) = d/GCD(a, b)
Que se encuentren N veces en el período de tiempo T 1 .
Entonces, el retraso de tiempo entre sus encuentros consecutivos es, digamos que T 2 se puede calcular como,
T 2 = (T 1 / N).
Este tiempo se puede calcular calculando el tiempo que se tarda en reunirse por primera vez después de que comiencen.
Entonces, el tiempo que tardaron en encontrarse por primera vez,
Por lo tanto, T 2 = (d / (a – b)).
Dividiendo T 1 por T 2 , obtenemos,
N = (T 1 / T 2 ) = ((a – b) / MCD(a, b))
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP Program to find number of distinct point of meet on a circular road
#include <bits/stdc++.h>
using namespace std;
// Returns the GCD of two number.
int gcd(int a, int b)
{
int c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
return b;
}
// Returns the number of distinct meeting points.
int numberOfmeet(int a, int b)
{
int ans;
// Find the relative speed.
if (a > b)
ans = a - b;
else
ans = b - a;
// convert the negative value to positive.
if (a < 0)
a = a * (-1);
if (b < 0)
b = b * (-1);
return ans / gcd(a, b);
}
// Driver Code
int main()
{
int a = 1, b = -1;
cout << numberOfmeet(a, b) << endl;
return 0;
}
Java
// Java Program to find number
// of distinct point of meet
// on a circular road
import java.io.*;
class GFG
{
// Returns the GCD
// of two number.
static int gcd(int a, int b)
{
int c = a % b;
while (c != 0)
{
a = b;
b = c;
c = a % b;
}
return b;
}
// Returns the number of
// distinct meeting points.
static int numberOfmeet(int a,
int b)
{
int ans;
// Find the relative speed.
if (a > b)
ans = a - b;
else
ans = b - a;
// convert the negative
// value to positive.
if (a < 0)
a = a * (-1);
if (b < 0)
b = b * (-1);
return ans / gcd(a, b);
}
// Driver Code
public static void main (String[] args)
{
int a = 1, b = -1;
System.out.println(numberOfmeet(a, b));
}
}
// This code is contributed by @ajit
Python3
# Python3 Program to find # number of distinct point # of meet on a circular road import math # Returns the number of # distinct meeting points. def numberOfmeet(a, b): ans = 0; # Find the relative speed. if (a > b): ans = a - b; else: ans = b - a; # convert the negative # value to positive. if (a < 0): a = a * (-1); if (b < 0): b = b * (-1); return int(ans / math.gcd(a, b)); # Driver Code a = 1; b = -1; print(numberOfmeet(a, b)); # This code is contributed by mits
C#
// C# Program to find number
// of distinct point of meet
// on a circular road
using System;
class GFG
{
// Returns the GCD
// of two number.
static int gcd(int a, int b)
{
int c = a % b;
while (c != 0)
{
a = b;
b = c;
c = a % b;
}
return b;
}
// Returns the number of
// distinct meeting points.
static int numberOfmeet(int a,
int b)
{
int ans;
// Find the relative speed.
if (a > b)
ans = a - b;
else
ans = b - a;
// convert the negative
// value to positive.
if (a < 0)
a = a * (-1);
if (b < 0)
b = b * (-1);
return ans / gcd(a, b);
}
// Driver Code
static public void Main ()
{
int a = 1, b = -1;
Console.WriteLine(
numberOfmeet(a, b));
}
}
// This code is contributed
// by @ajit
PHP
<?php
// PHP Program to find number
// of distinct point of meet
// on a circular road
// Returns the GCD of two number.
function gcd($a, $b)
{
$c = $a % $b;
while ($c != 0)
{
$a = $b;
$b = $c;
$c = $a % $b;
}
return $b;
}
// Returns the number of
// distinct meeting points.
function numberOfmeet($a, $b)
{
$ans;
// Find the relative speed.
if ($a > $b)
$ans = $a - $b;
else
$ans = $b - $a;
// convert the negative
// value to positive.
if ($a < 0)
$a = $a * (-1);
if ($b < 0)
$b = $b * (-1);
return $ans / gcd($a, $b);
}
// Driver Code
$a = 1;
$b = -1;
echo numberOfmeet($a, $b)."\n";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript Program to find number of distinct
// point of meet on a circular road
// Returns the GCD of two number.
function gcd(a, b)
{
var c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
return b;
}
// Returns the number of distinct meeting points.
function numberOfmeet(a, b)
{
var ans;
// Find the relative speed.
if (a > b)
ans = a - b;
else
ans = b - a;
// convert the negative value to positive.
if (a < 0)
a = a * (-1);
if (b < 0)
b = b * (-1);
return ans / gcd(a, b);
}
// Driver Code
var a = 1, b = -1;
document.write( numberOfmeet(a, b));
</script>
Producción:
2