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