Dada una coordenada (x, y) en un plano 2D. Tenemos que llegar a (x, y) desde la posición actual que está en el origen, es decir (0, 0). En cada paso, podemos movernos vertical u horizontalmente en el plano. Mientras nos movemos horizontalmente cada paso escribimos ‘H’ y mientras nos movemos verticalmente cada paso escribimos ‘V’. Por lo tanto, es posible que haya muchas strings que contengan ‘H’ y ‘V’, lo que representa una ruta de (0, 0) a (x, y). La tarea es encontrar lexicográficamente la K-ésima string más pequeña entre todas las strings posibles.
Ejemplos:
Entrada: x = 2, y = 2, k = 2
Salida: HVVH
Explicación: Hay 6 formas de llegar a (2, 2) desde (0, 0). La posible lista de strings ordenadas lexicográficamente: [“HHVV”, “HVHV”, “HVVH”, “VHHV”, “VHVH”, “VVHH”]. Por lo tanto, la segunda string lexicográficamente más pequeña es HVHV.
Entrada: x = 2, y = 2, k = 3
Salida: VHHV
Prerrequisitos: Formas de llegar a un punto desde el origen
Enfoque: La idea es utilizar la recursividad para resolver el problema. El número de formas de llegar a (x, y) desde el origen es x + y C x .
Ahora observe, el número de formas de llegar a (x, y) desde (1, 0) será (x + y – 1, x – 1) porque ya hemos dado un paso en la dirección horizontal, entonces 1 se resta de X. Además, el número de formas de llegar a (x, y) desde (0, 1) será (x + y – 1, y – 1) porque ya hemos dado un paso en la dirección vertical, por lo que se resta 1 de y . Dado que ‘H’ es lexicográficamente más pequeña que ‘V’, entre todas las strings, las strings iniciales contendrán ‘H’ al principio, es decir, los movimientos iniciales serán horizontales.
Entonces, si K <= x + y – 1 Cx – 1 , tomaremos ‘H’ como primer paso; de lo contrario, tomaremos ‘V’ como primer paso y resolveremos el número de idas a (x, y) desde (1, 0) será K = K – x + y – 1 C x – 1 .
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find Lexicographically Kth // smallest way to reach given coordinate from origin #include <bits/stdc++.h> using namespace std; // Return (a+b)!/a!b! int factorial(int a, int b) { int res = 1; // finding (a+b)! for (int i = 1; i <= (a + b); i++) res = res * i; // finding (a+b)!/a! for (int i = 1; i <= a; i++) res = res / i; // finding (a+b)!/b! for (int i = 1; i <= b; i++) res = res / i; return res; } // Return the Kth smallest way to reach given coordinate from origin void Ksmallest(int x, int y, int k) { // if at origin if (x == 0 && y == 0) return; // if on y-axis else if (x == 0) { // decrement y. y--; // Move vertical cout << "V"; // recursive call to take next step. Ksmallest(x, y, k); } // If on x-axis else if (y == 0) { // decrement x. x--; // Move horizontal. cout << "H"; // recursive call to take next step. Ksmallest(x, y, k); } else { // If x + y C x is greater than K if (factorial(x - 1, y) > k) { // Move Horizontal cout << "H"; // recursive call to take next step. Ksmallest(x - 1, y, k); } else { // Move vertical cout << "V"; // recursive call to take next step. Ksmallest(x, y - 1, k - factorial(x - 1, y)); } } } // Driven Program int main() { int x = 2, y = 2, k = 2; Ksmallest(x, y, k); return 0; }
Java
// Java Program to find // Lexicographically Kth // smallest way to reach // given coordinate from origin import java.io.*; class GFG { // Return (a+b)!/a!b! static int factorial(int a, int b) { int res = 1; // finding (a+b)! for (int i = 1; i <= (a + b); i++) res = res * i; // finding (a+b)!/a! for (int i = 1; i <= a; i++) res = res / i; // finding (a+b)!/b! for (int i = 1; i <= b; i++) res = res / i; return res; } // Return the Kth smallest // way to reach given // coordinate from origin static void Ksmallest(int x, int y, int k) { // if at origin if (x == 0 && y == 0) return; // if on y-axis else if (x == 0) { // decrement y. y--; // Move vertical System.out.print("V"); // recursive call to // take next step. Ksmallest(x, y, k); } // If on x-axis else if (y == 0) { // decrement x. x--; // Move horizontal. System.out.print("H"); // recursive call to // take next step. Ksmallest(x, y, k); } else { // If x + y C x is // greater than K if (factorial(x - 1, y) > k) { // Move Horizontal System.out.print( "H"); // recursive call to // take next step. Ksmallest(x - 1, y, k); } else { // Move vertical System.out.print("V"); // recursive call to // take next step. Ksmallest(x, y - 1, k - factorial(x - 1, y)); } } } // Driver Code public static void main (String[] args) { int x = 2, y = 2, k = 2; Ksmallest(x, y, k); } } // This code is contributed // by anuj_67.
Python3
# Python3 Program to find Lexicographically Kth # smallest way to reach given coordinate from origin # Return (a+b)!/a!b! def factorial(a, b): res = 1 # finding (a+b)! for i in range(1, a + b + 1): res = res * i # finding (a+b)!/a! for i in range(1, a + 1): res = res // i # finding (a+b)!/b! for i in range(1, b + 1): res = res // i return res # Return the Kth smallest way to reach # given coordinate from origin def Ksmallest(x, y, k): # if at origin if x == 0 and y == 0: return # if on y-axis elif x == 0: # decrement y. y -= 1 # Move vertical print("V", end = "") # recursive call to take next step. Ksmallest(x, y, k) # If on x-axis elif y == 0: # decrement x. x -= 1 # Move horizontal. print("H", end = "") # recursive call to take next step. Ksmallest(x, y, k) else: # If x + y C x is greater than K if factorial(x - 1, y) > k: # Move Horizontal print("H", end = "") # recursive call to take next step. Ksmallest(x - 1, y, k) else: # Move vertical print("V", end = "") # recursive call to take next step. Ksmallest(x, y - 1, k - factorial(x - 1, y)) # Driver Code if __name__ == "__main__": x, y, k = 2, 2, 2 Ksmallest(x, y, k) # This code is contributed by Rituraj Jain
C#
// C# Program to find // Lexicographically Kth // smallest way to reach // given coordinate from origin using System; class GFG { // Return (a+b)!/a!b! static int factorial(int a, int b) { int res = 1; // finding (a+b)! for (int i = 1; i <= (a + b); i++) res = res * i; // finding (a+b)!/a! for (int i = 1; i <= a; i++) res = res / i; // finding (a+b)!/b! for (int i = 1; i <= b; i++) res = res / i; return res; } // Return the Kth smallest // way to reach given // coordinate from origin static void Ksmallest(int x, int y, int k) { // if at origin if (x == 0 && y == 0) return; // if on y-axis else if (x == 0) { // decrement y. y--; // Move vertical Console.Write("V"); // recursive call to // take next step. Ksmallest(x, y, k); } // If on x-axis else if (y == 0) { // decrement x. x--; // Move horizontal. Console.Write("H"); // recursive call to // take next step. Ksmallest(x, y, k); } else { // If x + y C x is // greater than K if (factorial(x - 1, y) > k) { // Move Horizontal Console.Write( "H"); // recursive call to // take next step. Ksmallest(x - 1, y, k); } else { // Move vertical Console.Write("V"); // recursive call to // take next step. Ksmallest(x, y - 1, k - factorial(x - 1, y)); } } } // Driver Code public static void Main (String[] args) { int x = 2, y = 2, k = 2; Ksmallest(x, y, k); } } // This code is contributed by 29AjayKumar
PHP
<?php // PHP Program to find Lexicographically Kth // smallest way to reach given coordinate from origin // Return (a+b)!/a!b! function factorial($a, $b) { $res = 1; // finding (a+b)! for ($i = 1; $i <= ($a + $b); $i++) $res = $res * $i; // finding (a+b)!/a! for ($i = 1; $i <= $a; $i++) $res = $res / $i; // finding (a+b)!/b! for ($i = 1; $i <= $b; $i++) $res = $res / $i; return $res; } // Return the Kth smallest way to reach // given coordinate from origin function Ksmallest($x, $y, $k) { // if at origin if ($x == 0 && $y == 0) return; // if on y-axis else if ($x == 0) { // decrement y. $y--; // Move vertical echo("V"); // recursive call to // take next step. Ksmallest($x, $y, $k); } // If on x-axis else if ($y == 0) { // decrement x. $x--; // Move horizontal. echo("H"); // recursive call to // take next step. Ksmallest($x, $y, $k); } else { // If x + y C x is // greater than K if (factorial($x - 1, $y) > $k) { // Move Horizontal echo("H"); // recursive call to // take next step. Ksmallest($x - 1, $y, $k); } else { // Move vertical echo("V"); // recursive call to // take next step. Ksmallest($x, $y - 1, $k - factorial($x - 1, $y)); } } } // Driver Code $x = 2; $y = 2;$k = 2; Ksmallest($x, $y, $k); // This code is contributed // by Code_Mech. ?>
Javascript
<script> // Javascript Program to find Lexicographically Kth // smallest way to reach given coordinate from origin // Return (a+b)!/a!b! function factorial(a, b) { var res = 1; // finding (a+b)! for (var i = 1; i <= (a + b); i++) res = res * i; // finding (a+b)!/a! for (var i = 1; i <= a; i++) res = res / i; // finding (a+b)!/b! for (var i = 1; i <= b; i++) res = res / i; return res; } // Return the Kth smallest way to reach given coordinate from origin function Ksmallest(x, y, k) { // if at origin if (x == 0 && y == 0) return; // if on y-axis else if (x == 0) { // decrement y. y--; // Move vertical document.write( "V"); // recursive call to take next step. Ksmallest(x, y, k); } // If on x-axis else if (y == 0) { // decrement x. x--; // Move horizontal. document.write( "H"); // recursive call to take next step. Ksmallest(x, y, k); } else { // If x + y C x is greater than K if (factorial(x - 1, y) > k) { // Move Horizontal document.write( "H"); // recursive call to take next step. Ksmallest(x - 1, y, k); } else { // Move vertical document.write( "V"); // recursive call to take next step. Ksmallest(x, y - 1, k - factorial(x - 1, y)); } } } // Driven Program var x = 2, y = 2, k = 2; Ksmallest(x, y, k); // This code is contributed by rutvik_56. </script>
Producción
HVVH