Hay una pista circular de longitud N y dadas dos arrays start[] y direct[] de tamaño M y un entero T, donde start[ I ] representa el punto de inicio de la i -ésima persona y direct[ I ] representa la dirección, en el sentido de las agujas del reloj si direct[ I ] es 1 , en sentido contrario a las agujas del reloj si direct[ I ] es -1 , la tarea es encontrar las posiciones de todas las personas después de T unidades de tiempo.
Nota: Cada persona se mueve 1 unidad de distancia en 1 unidad de tiempo.
Ejemplos:
Entrada: N = 5, M = 2, T = 1, start[] = {2, 3}, direct[] = {1, -1} Salida: 3 2
Explicación :
El círculo dado tiene 5 puntos del 1 al 5 y hay dos hombres, digamos A y B. A comienza en el segundo punto y se mueve en el sentido de las agujas del reloj como direct[0] = 1, por lo que después de 1 minuto estará en el punto 3. De manera similar, B comienza en el tercer punto y se mueve en sentido antihorario, por lo que después de 1 min estará en el punto 2. Entonces, ans array contiene [3, 2] después de ordenar se convierte en [2, 3].Entrada: N = 4, M = 3, T = 2, inicio[] = {2, 1, 4}, directo[] = {-1, 1, -1} Salida: 4
3 2
Planteamiento: La idea para resolver este problema se basa en la observación de aprovechar el hecho de tener una pista circular. Encuentre el punto después de T unidades de tiempo y tome el módulo para encontrar la respuesta. Siga los pasos a continuación para resolver el problema:
- Itere sobre el rango [0, M) usando la variable i y realice las siguientes tareas:
- Inicialice la variable t_moves como direct[ I ]*T.
- Inicialice la variable end_pos como (((start[i] + t_moves) % N) + N) % N .
- Si end_pos es 0 , establezca el valor de start[ I ] como N ; de lo contrario, configúrelo como end_pos .
- Después de realizar los pasos anteriores, imprima los valores de la array start[] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <ctime>
#include <iostream>
using namespace std;
// Function to find the final position
// of men's after T minutes
int* positionAfterTMin(int N, int M, int T, int start[],
int direct[])
{
// Find the location of the i-th
// person after T minutes
for (int i = 0; i < M; i++)
{
// Total points moved m by i-th
// person in T minutes
int t_moves = direct[i] * T;
// As the path is circular then
// there is a chance that the
// person will traverse the same
// points again
int end_pos = (((start[i] + t_moves) % N) + N) % N;
// Storing location of the
// i-th person
start[i] = (end_pos == 0) ? N : end_pos;
}
// Returning array which contains
// location of every person moving
// in time T units
return start;
}
// Driver Code
int main()
{
int N = 4;
int M = 3;
int T = 2;
int start[] = { 2, 1, 4 };
int direct[] = { -1, 1, -1 };
int* ans = positionAfterTMin(N, M, T, start, direct);
for (int i = 0; i < M; i++) {
cout << *(ans + i) << " ";
}
return 0;
}
// This code is contributed by Kdheeraj.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the final position
// of men's after T minutes
public static int[] positionAfterTMin(
int N, int M, int T,
int[] start, int[] direct)
{
// Find the location of the i-th
// person after T minutes
for (int i = 0; i < M; i++) {
// Total points moved m by i-th
// person in T minutes
int t_moves = direct[i] * T;
// As the path is circular then
// there is a chance that the
// person will traverse the same
// points again
int end_pos
= (((start[i] + t_moves)
% N)
+ N)
% N;
// Storing location of the
// i-th person
start[i] = (end_pos == 0) ? N : end_pos;
}
// Returning array which contains
// location of every person moving
// in time T units
return start;
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
int M = 3;
int T = 2;
int[] start = { 2, 1, 4 };
int[] direct = { -1, 1, -1 };
int[] ans = positionAfterTMin(
N, M, T, start, direct);
for (int i = 0; i < ans.length; i++) {
System.out.print(ans[i] + " ");
}
}
}
Python3
# Python program for the above approach # Function to find the final position # of men's after T minutes def positionAfterTMin(N, M, T, start, direct): # Find the location of the i-th # person after T minutes for i in range(M): # Total points moved m by i-th # person in T minutes t_moves = direct[i] * T # As the path is circular then # there is a chance that the # person will traverse the same # points again end_pos = (((start[i] + t_moves) % N) + N) % N # Storing location of the # i-th person if end_pos == 0: start[i] = N else: start[i] = end_pos # Returning array which contains # location of every person moving # in time T units return start # Driver Code if __name__ == "__main__": N = 4 M = 3 T = 2 start = [2, 1, 4] direct = [-1, 1, -1] ans = positionAfterTMin(N, M, T, start, direct) print(ans) # This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the final position
// of men's after T minutes
public static int[] positionAfterTMin(
int N, int M, int T,
int[] start, int[] direct)
{
// Find the location of the i-th
// person after T minutes
for (int i = 0; i < M; i++) {
// Total points moved m by i-th
// person in T minutes
int t_moves = direct[i] * T;
// As the path is circular then
// there is a chance that the
// person will traverse the same
// points again
int end_pos
= (((start[i] + t_moves)
% N)
+ N)
% N;
// Storing location of the
// i-th person
start[i] = (end_pos == 0) ? N : end_pos;
}
// Returning array which contains
// location of every person moving
// in time T units
return start;
}
// Driver Code
public static void Main(String[] args)
{
int N = 4;
int M = 3;
int T = 2;
int[] start = { 2, 1, 4 };
int[] direct = { -1, 1, -1 };
int[] ans = positionAfterTMin(
N, M, T, start, direct);
for (int i = 0; i < ans.Length; i++) {
Console.Write(ans[i] + " ");
}
}
}
// This code is contributed by shivanisinghss2110
Javascript
// Javascript program for the above approach
// Function to find the final position
// of men's after T minutes
function positionAfterTMin(N, M, T, start, direct)
{
// Find the location of the i-th
// person after T minutes
for (let i = 0; i < M; i++)
{
// Total points moved m by i-th
// person in T minutes
let t_moves = direct[i] * T;
// As the path is circular then
// there is a chance that the
// person will traverse the same
// points again
let end_pos = (((start[i] + t_moves) % N) + N) % N;
// Storing location of the
// i-th person
start[i] = end_pos == 0 ? N : end_pos;
}
// Returning array which contains
// location of every person moving
// in time T units
return start;
}
// Driver Code
let N = 4;
let M = 3;
let T = 2;
let start = [2, 1, 4];
let direct = [-1, 1, -1];
let ans = positionAfterTMin(N, M, T, start, direct);
for (let i = 0; i < 3; i++) {
document.write(ans[i] + " ");
}
// This code is contributed by _saaurabh_jaiswal.
4 3 2
Tiempo Complejidad: O(M)
Espacio Auxiliar: O(1)