Dado un tamaño de cuadrícula N x M y una posición inicial (X, Y) y una serie de K movimientos.
Cada movimiento contiene 2 enteros Dx y Dy .
Un solo movimiento consiste en la siguiente operación que también se puede realizar tantas veces como sea posible:
X = X + Dx y Y = Y + Dy .
La tarea es contar el número de movimientos realizados.
Tenga en cuenta que en todo momento, la posición actual debe estar dentro de la cuadrícula.
Ejemplos:
Entrada: N = 4, M = 5, X = 1, Y = 1, k[] = {{1, 1}, {1, 1}, {0, -2}}
Salida: 4
Los valores de (X , Y) son los siguientes:
Pasos en el Movimiento 1: (1, 1) -> (2, 2) -> (3, 3) -> (4, 4) es decir, 3 movimientos
El Movimiento 2 no es posible porque no podemos mover a (5, 5) que está fuera de los límites de la cuadrícula
Pasos en el movimiento 3: (4, 4) -> (4, 2), es decir, un solo movimiento y (4, 0) estarán fuera de los límites, por lo que no más movimientos posibles.
Movimientos totales = 3 + 1 = 4
Entrada: N = 10, M = 10, X = 3, Y = 3, k[] = {{1, 1}, {-1, -1}}
Salida: 16
Enfoque: se puede observar que podemos manejar X e Y de forma independiente, y fusionarlos como número de pasos en el movimiento actual = mínimo de (número de pasos con X , número de pasos con Y ). Para encontrar el número de movimientos con X , podemos usar el signo de Dx para saber a qué extremo nos estamos acercando y encontrar la distancia a ese extremo, siendo la velocidad Dx , podemos encontrar el número de pasos que tomaría.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define int long long
using namespace std;
// Function to return the count of
// possible steps in a single direction
int steps(int cur, int x, int n)
{
// It can cover infinite steps
if (x == 0)
return INT_MAX;
// We are approaching towards X = N
if (x > 0)
return abs((n - cur) / x);
// We are approaching towards X = 1
else
return abs((cur - 1) / x);
}
// Function to return the count of steps
int countSteps(int curx, int cury, int n, int m,
vector<pair<int, int> > moves)
{
int count = 0;
int k = moves.size();
for (int i = 0; i < k; i++) {
int x = moves[i].first;
int y = moves[i].second;
// Take the minimum of both moves independently
int stepct
= min(steps(curx, x, n), steps(cury, y, m));
// Update count and current positions
count += stepct;
curx += stepct * x;
cury += stepct * y;
}
return count;
}
// Driver code
main()
{
int n = 4, m = 5, x = 1, y = 1;
vector<pair<int, int> > moves = { { 1, 1 },
{ 1, 1 },
{ 0, -2 } };
int k = moves.size();
cout << countSteps(x, y, n, m, moves);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to return the count of
// possible steps in a single direction
static int steps(int cur, int x, int n)
{
// It can cover infinite steps
if (x == 0)
return Integer.MAX_VALUE;
// We are approaching towards X = N
if (x > 0)
return Math.abs((n - cur) / x);
// We are approaching towards X = 1
else
return Math.abs((cur - 1) / x);
}
// Function to return the count of steps
static int countSteps(int curx, int cury,
int n, int m,
int[][] moves)
{
int count = 0;
int k = moves.length;
for (int i = 0; i < k; i++)
{
int x = moves[i][0];
int y = moves[i][1];
// Take the minimum of
// both moves independently
int stepct = Math.min(steps(curx, x, n),
steps(cury, y, m));
// Update count and current positions
count += stepct;
curx += stepct * x;
cury += stepct * y;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int n = 4, m = 5, x = 1, y = 1;
int[][] moves = { { 1, 1 }, { 1, 1 },
{ 0, -2 } };
System.out.print(countSteps(x, y, n, m, moves));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
# Function to return the count of
# possible steps in a single direction
def steps(cur, x, n):
# It can cover infinite steps
if x == 0:
return float('inf')
# We are approaching towards X = N
elif x > 0:
return abs((n - cur) // x)
# We are approaching towards X = 1
else:
return abs(int((cur - 1) / x))
# Function to return the count of steps
def countSteps(curx, cury, n, m, moves):
count = 0
k = len(moves)
for i in range(0, k):
x = moves[i][0]
y = moves[i][1]
# Take the minimum of both moves
# independently
stepct = min(steps(curx, x, n),
steps(cury, y, m))
# Update count and current positions
count += stepct
curx += stepct * x
cury += stepct * y
return count
# Driver code
if __name__ == "__main__":
n, m, x, y = 4, 5, 1, 1
moves = [[1, 1], [1, 1], [0, -2]]
print(countSteps(x, y, n, m, moves))
# This code is contributed
# by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the count of
// possible steps in a single direction
static int steps(int cur, int x, int n)
{
// It can cover infinite steps
if (x == 0)
return int.MaxValue;
// We are approaching towards X = N
if (x > 0)
return Math.Abs((n - cur) / x);
// We are approaching towards X = 1
else
return Math.Abs((cur - 1) / x);
}
// Function to return the count of steps
static int countSteps(int curx, int cury,
int n, int m,
int[,] moves)
{
int count = 0;
int k = moves.GetLength(0);
for (int i = 0; i < k; i++)
{
int x = moves[i, 0];
int y = moves[i, 1];
// Take the minimum of
// both moves independently
int stepct = Math.Min(steps(curx, x, n),
steps(cury, y, m));
// Update count and current positions
count += stepct;
curx += stepct * x;
cury += stepct * y;
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int n = 4, m = 5, x = 1, y = 1;
int[,] moves = { { 1, 1 }, { 1, 1 },
{ 0, -2 } };
Console.Write(countSteps(x, y, n, m, moves));
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// Php implementation of the above approach
// Function to return the count of
// possible steps in a single direction
function steps($cur, $x, $n)
{
// It can cover infinite steps
if ($x == 0)
return PHP_INT_MAX;
// We are approaching towards X = N
if ($x > 0)
return floor(abs(($n - $cur) / $x));
// We are approaching towards X = 1
else
return floor(abs(($cur - 1) / $x));
}
// Function to return the count of steps
function countSteps($curx, $cury, $n, $m, $moves)
{
$count = 0;
$k = sizeof($moves);
for ($i = 0; $i < $k; $i++)
{
$x = $moves[$i][0];
$y = $moves[$i][1];
// Take the minimum of both moves independently
$stepct = min(steps($curx, $x, $n), steps($cury, $y, $m));
// Update count and current positions
$count += $stepct;
$curx += $stepct * $x;
$cury += $stepct * $y;
}
return $count;
}
// Driver code
$n = 4 ;
$m = 5 ;
$x = 1 ;
$y = 1 ;
$moves = array( array( 1, 1 ),
array( 1, 1 ),
array( 0, -2 ) );
$k = sizeof($moves);
echo countSteps($x, $y, $n, $m, $moves);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to return the count of
// possible steps in a single direction
function steps(cur, x, n)
{
// It can cover infinite steps
if (x == 0)
return Number.MAX_VALUE;
// We are approaching towards X = N
if (x > 0)
return Math.abs((n - cur) / x);
// We are approaching towards X = 1
else
return Math.abs((cur - 1) / x);
}
// Function to return the count of steps
function countSteps(curx, cury, n, m, moves)
{
let count = 0;
let k = moves.length;
for (let i = 0; i < k; i++)
{
let x = moves[i][0];
let y = moves[i][1];
// Take the minimum of
// both moves independently
let stepct = Math.min(steps(curx, x, n),
steps(cury, y, m));
// Update count and current positions
count += stepct;
curx += stepct * x;
cury += stepct * y;
}
return Math.floor(count);
}
// driver program
let n = 4, m = 5, x = 1, y = 1;
let moves = [[ 1, 1 ], [ 1, 1 ],
[ 0, -2 ]];
document.write(countSteps(x, y, n, m, moves));
</script>
4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA