Dada una string S que representa una secuencia de movimientos ( L , R , U y D ) y un número entero R que representa el radio de un círculo cuyo centro es el origen (0, 0) , la tarea es comprobar si es posible llegar a cualquier punto de la circunferencia del círculo dado desde el origen eligiendo cualquier subsecuencia de movimientos de la cuerda S . Si es posible llegar a un punto en la circunferencia, escriba «Sí» . De lo contrario, escriba “No” .
Las operaciones requeridas a realizar para cada dirección son las siguientes:
- Si el carácter actual es L , disminuya la coordenada x en 1 .
- Si el carácter actual es R , entonces incremente la coordenada x en 1 .
- Si el carácter actual es U , entonces incremente la coordenada y en 1 .
- Si el carácter actual es D , disminuya la coordenada y en 1 .
Ejemplos:
Entrada: S = “LLRULD”, R = 3
Salida: Si
Explicación:
Seleccionando la subsecuencia “LLL”, el cambio de coordenadas al realizar la secuencia de movimientos son:
(0, 0) → (-1, 0) → (- 2, 0) → (-3, 0)
Dado que (-3, 0) se encuentra en la circunferencia del círculo dado, es posible llegar a laEntrada: S = “ULRDLD”, R = 6
Salida: No
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la string S dada y si existe alguna subsecuencia de movimientos que resulten en alcanzar la circunferencia del círculo desde el origen (0, 0) , imprima «Sí» . De lo contrario, escriba “No” .
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- Dado que la ruta que debe considerarse comienza desde el origen (0, 0) , si el recuento máximo entre cada uno de los caracteres L , R , U y D en la string tiene un valor superior a R , entonces la ruta desde el origen hasta la circunferencia del círculo existe.
- Si existen dos valores X e Y tales que la suma de los cuadrados de X e Y es R 2 , entonces existe un camino triangular desde el origen hasta la circunferencia del círculo.
Siga los pasos a continuación para resolver el problema dado:
- Almacene el recuento de caracteres L , R , U y D , en la string S dada en una variable, digamos cntL , cntR , cntU y cntD respectivamente.
- Si el máximo de cntL , cntR , cntU y cntD es al menos R , entonces existe una trayectoria en línea recta desde el origen hasta la circunferencia. Por lo tanto, imprima “Sí” .
- Si el cuadrado del máximo de cntL y cntR y el máximo de cntU y cntD es al menos R 2 , imprima «Sí», ya que existe un camino triangular desde el origen hasta la circunferencia del círculo.
- Si no se presenta ninguno de los casos anteriores, escriba “No” .
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 it is possible
// to reach any point on circumference
// of the given circle from (0,0)
string isPossible(string S, int R, int N)
{
// Stores the count of 'L', 'R'
int cntl = 0, cntr = 0;
// Stores the count of 'U', 'D'
int cntu = 0, cntd = 0;
// Traverse the string S
for (int i = 0; i < N; i++) {
// Update the count of L
if (S[i] == 'L')
cntl++;
// Update the count of R
else if (S[i] == 'R')
cntr++;
// Update the count of U
else if (S[i] == 'U')
cntu++;
// Update the count of D
else
cntd++;
}
// Condition 1 for reaching
// the circumference
if (max(max(cntl, cntr), max(cntu, cntd)) >= R)
return "Yes";
unordered_map<int, int> mp;
int r_square = R * R;
for (int i = 1; i * i <= r_square; i++) {
// Store the value
// of (i * i) in the Map
mp[i * i] = i;
// Check if (r_square - i*i)
// already present in HashMap
if (mp.find(r_square - i * i) != mp.end()) {
// If it is possible to reach the
// point (± mp[r_square - i*i], ± i)
if (max(cntl, cntr)
>= mp[r_square - i * i]
&& max(cntu, cntd) >= i)
return "Yes";
// If it is possible to reach the
// point (±i, ±mp[r_square-i*i])
if (max(cntl, cntr) >= i
&& max(cntu, cntd)
>= mp[r_square - i * i])
return "Yes";
}
}
// If it is impossible to reach
return "No";
}
// Driver Code
int main()
{
string S = "RDLLDDLDU";
int R = 5;
int N = S.length();
cout << isPossible(S, R, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if it is possible
// to reach any point on circumference
// of the given circle from (0,0)
static String isPossible(String S, int R, int N)
{
// Stores the count of 'L', 'R'
int cntl = 0, cntr = 0;
// Stores the count of 'U', 'D'
int cntu = 0, cntd = 0;
// Traverse the string S
for(int i = 0; i < N; i++)
{
// Update the count of L
if (S.charAt(i) == 'L')
cntl++;
// Update the count of R
else if (S.charAt(i) == 'R')
cntr++;
// Update the count of U
else if (S.charAt(i) == 'U')
cntu++;
// Update the count of D
else
cntd++;
}
// Condition 1 for reaching
// the circumference
if (Math.max(Math.max(cntl, cntr),
Math.max(cntu, cntd)) >= R)
return "Yes";
HashMap<Integer, Integer> mp = new HashMap<>();
int r_square = R * R;
for(int i = 1; i * i <= r_square; i++)
{
// Store the value
// of (i * i) in the Map
mp.put(i * i, i);
// Check if (r_square - i*i)
// already present in HashMap
if (mp.containsKey(r_square - i * i))
{
// If it is possible to reach the
// point (± mp[r_square - i*i], ± i)
if (Math.max(cntl, cntr) >=
mp.get(r_square - i * i) &&
Math.max(cntu, cntd) >= i)
return "Yes";
// If it is possible to reach the
// point (±i, ±mp[r_square-i*i])
if (Math.max(cntl, cntr) >= i &&
Math.max(cntu, cntd) >=
mp.get(r_square - i * i))
return "Yes";
}
}
// If it is impossible to reach
return "No";
}
// Driver Code
public static void main(String[] args)
{
String S = "RDLLDDLDU";
int R = 5;
int N = S.length();
System.out.println(isPossible(S, R, N));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to check if it is possible
# to reach any point on circumference
# of the given circle from (0,0)
def isPossible(S, R, N):
# Stores the count of 'L', 'R'
cntl = 0
cntr = 0
# Stores the count of 'U', 'D'
cntu = 0
cntd = 0
# Traverse the string S
for i in range(N):
# Update the count of L
if (S[i] == 'L'):
cntl += 1
# Update the count of R
elif (S[i] == 'R'):
cntr += 1
# Update the count of U
elif (S[i] == 'U'):
cntu += 1
# Update the count of D
else:
cntd += 1
# Condition 1 for reaching
# the circumference
if (max(max(cntl, cntr), max(cntu, cntd)) >= R):
return "Yes"
mp = {}
r_square = R * R
i = 1
while i * i <= r_square:
# Store the value
# of (i * i) in the Map
mp[i * i] = i
# Check if (r_square - i*i)
# already present in HashMap
if ((r_square - i * i) in mp):
# If it is possible to reach the
# point (± mp[r_square - i*i], ± i)
if (max(cntl, cntr) >= mp[r_square - i * i] and
max(cntu, cntd) >= i):
return "Yes"
# If it is possible to reach the
# point (±i, ±mp[r_square-i*i])
if (max(cntl, cntr) >= i and
max(cntu, cntd) >= mp[r_square - i * i]):
return "Yes"
i += 1
# If it is impossible to reach
return "No"
# Driver Code
if __name__ == "__main__":
S = "RDLLDDLDU"
R = 5
N = len(S)
print(isPossible(S, R, N))
# This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check if it is possible
// to reach any point on circumference
// of the given circle from (0,0)
static string isPossible(string S, int R, int N)
{
// Stores the count of 'L', 'R'
int cntl = 0, cntr = 0;
// Stores the count of 'U', 'D'
int cntu = 0, cntd = 0;
// Traverse the string S
for(int i = 0; i < N; i++)
{
// Update the count of L
if (S[i] == 'L')
cntl++;
// Update the count of R
else if (S[i] == 'R')
cntr++;
// Update the count of U
else if (S[i] == 'U')
cntu++;
// Update the count of D
else
cntd++;
}
// Condition 1 for reaching
// the circumference
if (Math.Max(Math.Max(cntl, cntr),
Math.Max(cntu, cntd)) >= R)
return "Yes";
Dictionary<int, int> mp = new Dictionary<int, int>();
int r_square = R * R;
for(int i = 1; i * i <= r_square; i++)
{
// Store the value
// of (i * i) in the Map
mp.Add(i * i, i);
// Check if (r_square - i*i)
// already present in HashMap
if (mp.ContainsKey(r_square - i * i))
{
// If it is possible to reach the
// point (± mp[r_square - i*i], ± i)
if (Math.Max(cntl, cntr) >=
mp[r_square - i * i] &&
Math.Max(cntu, cntd) >= i)
return "Yes";
// If it is possible to reach the
// point (±i, ±mp[r_square-i*i])
if (Math.Max(cntl, cntr) >= i &&
Math.Max(cntu, cntd) >=
mp[r_square - i * i])
return "Yes";
}
}
// If it is impossible to reach
return "No";
}
static public void Main ()
{
string S = "RDLLDDLDU";
int R = 5;
int N = S.Length;
Console.WriteLine(isPossible(S, R, N));
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript program for the above approach
// Function to check if it is possible
// to reach any point on circumference
// of the given circle from (0,0)
function isPossible(S, R, N)
{
// Stores the count of 'L', 'R'
var cntl = 0, cntr = 0;
// Stores the count of 'U', 'D'
var cntu = 0, cntd = 0;
// Traverse the string S
for (var i = 0; i < N; i++) {
// Update the count of L
if (S[i] == 'L')
cntl++;
// Update the count of R
else if (S[i] == 'R')
cntr++;
// Update the count of U
else if (S[i] == 'U')
cntu++;
// Update the count of D
else
cntd++;
}
// Condition 1 for reaching
// the circumference
if (Math.max(Math.max(cntl, cntr), Math.max(cntu, cntd)) >= R)
return "Yes";
var mp = new Map();
var r_square = R * R;
for (var i = 1; i * i <= r_square; i++) {
// Store the value
// of (i * i) in the Map
mp.set(i * i, i);
// Check if (r_square - i*i)
// already present in HashMap
if (mp.has(r_square - i * i)) {
// If it is possible to reach the
// point (± mp[r_square - i*i], ± i)
if (Math.max(cntl, cntr)
>= mp.get(r_square - i * i)
&& Math.max(cntu, cntd) >= i)
return "Yes";
// If it is possible to reach the
// point (±i, ±mp[r_square-i*i])
if (Math.max(cntl, cntr) >= i
&& Math.max(cntu, cntd)
>= mp.get(r_square - i * i))
return "Yes";
}
}
// If it is impossible to reach
return "No";
}
// Driver Code
var S = "RDLLDDLDU";
var R = 5;
var N = S.length;
document.write( isPossible(S, R, N));
</script>
Producción:
Yes
Complejidad temporal: O(N + R)
Espacio auxiliar: O(R 2 )
Publicación traducida automáticamente
Artículo escrito por kundudinesh007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA