Dado un entero positivo N y coordenadas (X, Y) , la tarea es comprobar si es posible llegar a (X, Y) desde (0, 0) con el salto de 1 y N simultáneamente en la dirección perpendicular. Si es posible llegar a (X, Y) , imprima Sí . De lo contrario , imprima No.
Ejemplos:
Entrada: N = 2, X = 5, Y = 4
Salida: Sí
Explicación:
Los siguientes son los posibles movimientos que conducen al punto (X, Y) desde la coordenada actual (0, 0):
- Al realizar el salto de (2, 1) desde la coordenada actual se modifica a (2, 1).
- Al realizar el salto de (2, 1) desde la coordenada actual se modifica a (4, 2).
- Al realizar el salto de (1, 2) desde la coordenada actual se modifica a (5, 4).
Entrada: N = 3, X = 5, Y = 4
Salida: No
Enfoque: el problema dado se puede resolver en base a la observación de que hay 4 formas posibles de saltar desde cualquier coordenada que son (1, N), (1, -N), (-1, N) y (-1, -N) . Además, el problema se puede dividir en 3 casos diferentes:
- Caso 1: donde N es par : en tales casos, se puede alcanzar cualquier coordenada (X, Y). Consideremos X e Y uno a la vez. Para una coordenada X,se puede seguir la secuencia de (1, N), (1, -N), (1, N), (1, -N),… saltos. La coordenada resultante será (X, 0), que es la coordenada deseada, o (X, N) . Como N es par, también se puede seguirla secuencia de saltos (N, -1), (-N, -1), (N, -1), (N, -1),… para llegar a (X, 0) . De manera similar,se puede alcanzar (0, Y) , y combinando la secuencia de saltos para alcanzar (X, 0) y (0, Y), se puede alcanzar (X, Y).
- Caso 2: donde N es impar y tanto X como Y son pares o impares : estos casos se pueden manejar siguiendo una secuencia de operaciones similar al Caso 1 .
- Caso 3 – donde N es impar y X e Y tienen diferente paridad : En tales casos, no hay secuencia posible de saltos para alcanzar (X, Y) porque según el Caso 2, (X + 1, Y) y (X, Y + 1) debe ser alcanzable ya que ambos tendrán la misma paridad y no hay secuencia posible de operaciones para cubrir una distancia de (1, 0) o (0, 1) .
Por lo tanto, el único caso en el que no es posible llegar a (X, Y) desde (0, 0) es cuando N es impar y X e Y tienen paridad diferente, es decir, X es par e Y es impar o viceversa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if (X, Y) is reachable
// from (0, 0) using the jumps of given type
string checkReachability(int N, int X, int Y)
{
// Case where source & destination
// are the same
if (X == 0 && Y == 0) {
return "YES";
}
// Check for even N (X, Y) is
// reachable or not
if (N % 2 == 0) {
return "YES";
}
// If N is odd and parity of X and
// Y is different return, no valid
// sequence of jumps exist
else {
if (X % 2 != Y % 2) {
return "NO";
}
else {
return "YES";
}
}
}
// Driver Code
int main()
{
int N = 2;
int X = 5, Y = 4;
cout << checkReachability(N, X, Y);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Function to check if (X, Y) is reachable
// from (0, 0) using the jumps of given type
static String checkReachability(int N, int X, int Y)
{
// Case where source & destination
// are the same
if (X == 0 && Y == 0) {
return "YES";
}
// Check for even N (X, Y) is
// reachable or not
if (N % 2 == 0) {
return "YES";
}
// If N is odd and parity of X and
// Y is different return, no valid
// sequence of jumps exist
else {
if (X % 2 != Y % 2) {
return "NO";
}
else {
return "YES";
}
}
}
// Driver Code
public static void main (String[] args) {
int N = 2;
int X = 5, Y = 4;
System.out.println(checkReachability(N, X, Y));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to check if (X, Y) is reachable # from (0, 0) using the jumps of given type def checkReachability(N, X, Y): # Case where source & destination # are the same if (X == 0 and Y == 0): return "YES" # Check for even N (X, Y) is # reachable or not if (N % 2 == 0): return "YES" # If N is odd and parity of X and # Y is different return, no valid # sequence of jumps exist else: if (X % 2 != Y % 2): return "NO" else: return "YES" # Driver Code if __name__ == '__main__': N = 2 X = 5 Y = 4 print(checkReachability(N, X, Y)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# code for the above approach
using System;
class GFG
{
// Function to check if (X, Y) is reachable
// from (0, 0) using the jumps of given type
static string checkReachability(int N, int X, int Y)
{
// Case where source & destination
// are the same
if (X == 0 && Y == 0) {
return "YES";
}
// Check for even N (X, Y) is
// reachable or not
if (N % 2 == 0) {
return "YES";
}
// If N is odd and parity of X and
// Y is different return, no valid
// sequence of jumps exist
else {
if (X % 2 != Y % 2) {
return "NO";
}
else {
return "YES";
}
}
}
// Driver Code
public static void Main (string[] args) {
int N = 2;
int X = 5, Y = 4;
Console.WriteLine(checkReachability(N, X, Y));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Function to check if (X, Y) is reachable
// from (0, 0) using the jumps of given type
string checkReachability(int N, int X, int Y)
{
// Case where source & destination
// are the same
if (X == 0 && Y == 0) {
return "YES";
}
// Check for even N (X, Y) is
// reachable or not
if (N % 2 == 0) {
return "YES";
}
// If N is odd and parity of X and
// Y is different return, no valid
// sequence of jumps exist
else {
if (X % 2 != Y % 2) {
return "NO";
}
else {
return "YES";
}
}
}
// Driver Code
let N = 2, X = 5, Y = 4;
document.write(checkReachability(N, X, Y));
// This code is contributed by dwivediyash.
</script>
Producción:
YES
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA