Recuento de todas las formas posibles de alcanzar un objetivo por un Caballero

Posted on by Rudeus Greyrat

Dados dos números enteros N , M que denotan N×M tablero de ajedrez, la tarea es contar el número de formas en que un caballo puede llegar a (N, M) a partir de (0, 0) . Dado que la respuesta puede ser muy grande, imprima la respuesta módulo 10 9 +7 .

Ejemplo:

Entrada: N =3, M= 3
Salida: 2
Explicación: Las 
dos formas de llegar a (3, 3) desde (0, 0) son las siguientes:
(0, 0) → (1, 2) → (3, 3)
(0, 0) → (2, 1) → (3, 3)
 
Entrada: N=4, M=3
Salida: 0
Explicación: No existe forma posible de llegar a (4, 3) desde (0, 0).

Enfoque : la idea aquí es observar el patrón de que cada movimiento incrementa el valor de la coordenada x + el valor de la coordenada y en 3. Siga los pasos a continuación para resolver el problema.

  1. Si (N + M) no es divisible por 3 , entonces no existe ningún camino posible.
  2. Si (N + M) % 3==0 , cuente el número de movimientos de tipo (+1, +2) , es decir, X y cuente el número de movimientos de tipo (+2, +1) , es decir, Y.
  3. Encuentre la ecuación del tipo (+1, +2) es decir , X + 2Y = N
  4. Encuentre la ecuación del tipo (+2, +1) es decir , 2X + Y = M
  5. Encuentre los valores calculados de X e Y , si X < 0 o Y < 0 , entonces no existe una ruta posible.
  6. De lo contrario, calcule ( X+Y ) C Y .

A continuación se muestra la implementación del enfoque anterior:

C++14

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int Mod = 1e9 + 7;
 
// Function to return X^Y % Mod
int power(int X, int Y, int Mod)
{
 
    // Base Case
    if (Y == 0)
        return 1;
 
    int p = power(X, Y / 2, Mod) % Mod;
    p = (p * p) % Mod;
 
    if (Y & 1) {
        p = (X * p) % Mod;
    }
 
    return p;
}
 
// Function to return the
// inverse of factorial of N
int Inversefactorial(int N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    int fact = 1;
 
    for (int i = 1; i <= N; i++) {
        fact = (fact * i) % Mod;
    }
 
    return power(fact, Mod - 2, Mod);
}
 
// Function to return factorial
// of n % Mod
int factorial(int N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    int fact = 1;
 
    for (int i = 1; i <= N; i++) {
        fact = (fact * i) % Mod;
    }
 
    return fact;
}
 
// Function to return  the value
// of n! / (( n- k)! * k!)
int nck(int N, int K)
{
    int factN = factorial(N);
    int inv = Inversefactorial(K);
    int invFact = Inversefactorial(N - K);
    return (((factN * inv) % Mod) * invFact) % Mod;
}
 
// Function to return the count of
// ways to reach (n, m) from (0, 0)
int TotalWaYs(int N, int M)
{
 
    // If (N + M) % 3 != 0
    if ((N + M) % 3 != 0)
 
        // No possible way exists
        return 0;
 
    // Calculate X and Y from the
    // equations X + 2Y = N
    // and 2X + Y == M
    int X = N - (N + M) / 3;
    int Y = M - (N + M) / 3;
 
    if (X < 0 || Y < 0)
        return 0;
 
    return nck(X + Y, Y);
}
 
// Driver Code
int main()
{
 
    int N = 3, M = 3;
 
    cout << TotalWaYs(N, M);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
static int Mod = (int) (1e9 + 7);
 
// Function to return X^Y % Mod
static int power(int X, int Y, int Mod)
{
 
    // Base Case
    if (Y == 0)
        return 1;
 
    int p = power(X, Y / 2, Mod) % Mod;
    p = (p * p) % Mod;
 
    if ((Y & 1) != 0)
    {
        p = (X * p) % Mod;
    }
 
    return p;
}
 
// Function to return the
// inverse of factorial of N
static int Inversefactorial(int N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    int fact = 1;
 
    for (int i = 1; i <= N; i++)
    {
        fact = (fact * i) % Mod;
    }
 
    return power(fact, Mod - 2, Mod);
}
 
// Function to return factorial
// of n % Mod
static int factorial(int N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    int fact = 1;
 
    for (int i = 1; i <= N; i++)
    {
        fact = (fact * i) % Mod;
    }
 
    return fact;
}
 
// Function to return  the value
// of n! / (( n- k)! * k!)
static int nck(int N, int K)
{
    int factN = factorial(N);
    int inv = Inversefactorial(K);
    int invFact = Inversefactorial(N - K);
    return (((factN * inv) % Mod) * invFact) % Mod;
}
 
// Function to return the count of
// ways to reach (n, m) from (0, 0)
static int TotalWaYs(int N, int M)
{
 
    // If (N + M) % 3 != 0
    if (((N + M) % 3 )!= 0)
 
        // No possible way exists
        return 0;
 
    // Calculate X and Y from the
    // equations X + 2Y = N
    // and 2X + Y == M
    int X = N - (N + M) / 3;
    int Y = M - (N + M) / 3;
 
    if (X < 0 || Y < 0)
        return 0;
 
    return nck(X + Y, Y);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3, M = 3;
 
    System.out.print(TotalWaYs(N, M));
}
}
 
// This code is contributed by Rohit_ranjan

Python3

# Python3 program to implement
# above approach
Mod = int(1e9 + 7)
 
# Function to return X^Y % Mod
def power(X, Y, Mod):
     
    # Base case
    if Y == 0:
        return 1
         
    p = power(X, Y // 2, Mod) % Mod
    p = (p * p) % Mod
     
    if Y & 1:
        p = (X * p) % Mod
         
    return p
 
# Function to return the
# inverse of factorial of N
def Inversefactorial(N):
     
    # Base case
    if N <= 0:
        return 1
     
    fact = 1
    for i in range(1, N + 1):
        fact = (fact * i) % Mod
         
    return power(fact, Mod - 2, Mod)
 
# Function to return factorial
# of n % Mod
def factorial(N):
     
    # Base case
    if N <= 0:
        return 1
     
    fact = 1
    for i in range(1, N + 1):
        fact = (fact * i) % Mod
     
    return fact
 
# Function to return the value
# of n! / (( n- k)! * k!)
def nck(N, K):
     
    factN = factorial(N)
    inv = Inversefactorial(K)
    invFact = Inversefactorial(N - K)
     
    return (((factN * inv) % Mod) * invFact) % Mod
 
# Function to return the count of
# ways to reach (n, m) from (0, 0)
def TotalWays(N, M):
     
    # If (N + M) % 3 != 0
    if (N + M) % 3 != 0:
         
        # No possible way exists
        return 0
     
    # Calculate X and Y from the
    # equations X + 2Y = N
    # and 2X + Y == M
    X = N - (N + M) // 3
    Y = M - (N + M) // 3
     
    if X < 0 or Y < 0:
        return 0
         
    return nck(X + Y, Y)
 
# Driver code
N, M = 3, 3
 
print(TotalWays(N, M))
 
# This code is contributed by Stuti Pathak

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
static int Mod = (int)(1e9 + 7);
 
// Function to return X^Y % Mod
static int power(int X, int Y, int Mod)
{
 
    // Base Case
    if (Y == 0)
        return 1;
 
    int p = power(X, Y / 2, Mod) % Mod;
    p = (p * p) % Mod;
 
    if ((Y & 1) != 0)
    {
        p = (X * p) % Mod;
    }
    return p;
}
 
// Function to return the
// inverse of factorial of N
static int Inversefactorial(int N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    int fact = 1;
 
    for(int i = 1; i <= N; i++)
    {
        fact = (fact * i) % Mod;
    }
    return power(fact, Mod - 2, Mod);
}
 
// Function to return factorial
// of n % Mod
static int factorial(int N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    int fact = 1;
 
    for(int i = 1; i <= N; i++)
    {
        fact = (fact * i) % Mod;
    }
    return fact;
}
 
// Function to return the value
// of n! / (( n- k)! * k!)
static int nck(int N, int K)
{
    int factN = factorial(N);
    int inv = Inversefactorial(K);
    int invFact = Inversefactorial(N - K);
    return (((factN * inv) % Mod) * invFact) % Mod;
}
 
// Function to return the count of
// ways to reach (n, m) from (0, 0)
static int TotalWaYs(int N, int M)
{
 
    // If (N + M) % 3 != 0
    if (((N + M) % 3 ) != 0)
 
        // No possible way exists
        return 0;
 
    // Calculate X and Y from the
    // equations X + 2Y = N
    // and 2X + Y == M
    int X = N - (N + M) / 3;
    int Y = M - (N + M) / 3;
 
    if (X < 0 || Y < 0)
        return 0;
 
    return nck(X + Y, Y);
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 3, M = 3;
 
    Console.Write(TotalWaYs(N, M));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript Program to implement
// the above approach
 
var Mod = 1000000007;
 
// Function to return X^Y % Mod
function power(X, Y, Mod)
{
 
    // Base Case
    if (Y == 0)
        return 1;
 
    var p = power(X, Y / 2, Mod) % Mod;
    p = (p * p) % Mod;
 
    if (Y & 1) {
        p = (X * p) % Mod;
    }
 
    return p;
}
 
// Function to return the
// inverse of factorial of N
function Inversefactorial(N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    var fact = 1;
 
    for (var i = 1; i <= N; i++) {
        fact = (fact * i) % Mod;
    }
 
    return power(fact, Mod - 2, Mod);
}
 
// Function to return factorial
// of n % Mod
function factorial(N)
{
 
    // Base case
    if (N <= 0)
        return 1;
 
    var fact = 1;
 
    for (var i = 1; i <= N; i++) {
        fact = (fact * i) % Mod;
    }
 
    return fact;
}
 
// Function to return  the value
// of n! / (( n- k)! * k!)
function nck( N, K)
{
    var factN = factorial(N);
    var inv = Inversefactorial(K);
    var invFact = Inversefactorial(N - K);
    return (((factN * inv) % Mod) * invFact) % Mod;
}
 
// Function to return the count of
// ways to reach (n, m) from (0, 0)
function TotalWaYs(N, M)
{
 
    // If (N + M) % 3 != 0
    if ((N + M) % 3 != 0)
 
        // No possible way exists
        return 0;
 
    // Calculate X and Y from the
    // equations X + 2Y = N
    // and 2X + Y == M
    var X = N - (N + M) / 3;
    var Y = M - (N + M) / 3;
 
    if (X < 0 || Y < 0)
        return 0;
 
    return nck(X + Y, Y);
}
 
// Driver Code
var N = 3, M = 3;
document.write( TotalWaYs(N, M));
 
</script>
Producción: 

2

 

Complejidad temporal: O(X + Y + log(mod)).
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por __mahakal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *