Un artículo que contiene preguntas recientes de la ronda de programación de Directi en las ubicaciones de mi campus y también en las universidades de mis amigos.
1) Se le da una string S. Cada carácter de S es ‘a’ o ‘b’. Desea invertir exactamente una substring de S de modo que la nueva string sea lexicográficamente más pequeña que todas las demás strings que puede obtener al invertir exactamente una substring.
Por ejemplo, dado ‘abab’, puede optar por invertir la substring ‘ab’ que comienza en el índice 2 (basado en 0). Esto le da la string ‘abba’. Pero, si elige invertir la substring ‘ba’ a partir del índice 1, obtendrá ‘aabb’. No hay forma de obtener una string más pequeña, por lo tanto, invertir la substring en el rango [1, 2] es óptimo.
Entrada La
primera línea contiene un número T, el número de casos de prueba.
Cada caso de prueba contiene una sola string S. Los caracteres de la string serán del conjunto {a, b}.
Salida
Para cada caso de prueba, imprima dos números separados por comas; por ejemplo “x,y” (sin las comillas y sin ningún espacio en blanco adicional). “x,y” describe el índice inicial (basado en 0) y el índice final respectivamente de la substring que debe invertirse para lograr la string lexicográfica más pequeña. Si hay múltiples respuestas posibles, imprima la que tenga la ‘x’ más pequeña. Si todavía hay múltiples respuestas posibles, imprima la que tenga la ‘y’ más pequeña.
Restricciones
1 <= T <= 100
1 <= longitud de S <= 1000
Entrada de muestra
5
abab
abba
bbaa
aaaa
babaabba
Salida
de muestra 1,2
1,3
0,3
0,0
0,4
2) Dadas dos strings I y F, donde I es el estado inicial y F es el estado final. Cada estado contendrá ‘a’, ‘b’ y solo un espacio vacío representado por ‘_’. Su tarea es pasar del estado inicial al estado final con el mínimo número de operaciones.
Las operaciones permitidas son
1. Puede intercambiar caracteres vacíos con cualquier carácter adyacente. (Por ejemplo, ‘aba_ab’ se puede convertir en ‘ab_aab’ o ‘abaa_b’).
2. Puede intercambiar un carácter vacío con el que está al lado del carácter adyacente solo si el carácter adyacente es diferente del que está al lado del carácter adyacente. (Por ejemplo, ‘aba_ab’ se puede convertir en ‘a_abab’ o ‘ababa_’, pero ‘ab_aab’ no se puede convertir en ‘abaa_b’, porque ‘a’ no puede saltar sobre ‘a’).
Aporte
La primera línea contiene un solo entero T: el número de casos de prueba (menos de 25). Los casos de prueba T siguen.
Cada caso de prueba contiene dos strings I y F en dos líneas diferentes, donde I es el estado inicial y F es el estado final. I y F pueden ser iguales. Su longitud siempre será igual. Su longitud será de al menos 2. Su longitud nunca será superior a 20.
Salida
Para cada caso de prueba, se genera una sola línea que contiene el número mínimo de pasos necesarios para alcanzar el estado final desde el estado inicial. Puede suponer que siempre es posible alcanzar el estado final desde el estado inicial. Puede suponer que ninguna respuesta es más de 30. Entrada de
ejemplo
:
2
a_b
ab_
aba_a
_baaa
Salida:
1
2
3) Se genera un recorrido de preorden probabilístico para un árbol de búsqueda binario a partir del siguiente pseudocódigo
function preorder(u) {
if u is null then return
print u.label
r = either 0 or 1 with 50% probability
if r == 0
preorder(u.left_child)
preorder(u.right_child)
if r == 1
preorder(u.right_child)
preorder(u.left_child)
}
Dados los recorridos de preorden de un árbol de búsqueda binaria, siempre puede construir de forma única el árbol de búsqueda binaria. Dado que, el recorrido en orden de un árbol de búsqueda binario es, por supuesto, la lista ordenada de etiquetas.
Dado uno de los recorridos de orden previo probabilístico de algún árbol de búsqueda binario, imprima el número de recorridos de orden previo probabilístico diferentes que el algoritmo anterior podría generar. Consulte la sección de explicación para mayor claridad.
Entrada
La primera línea de la entrada es igual a N, el número de casos de prueba. Luego sigue la descripción de N casos de prueba. La primera línea en cada caso de prueba es el número entero N, el número de Nodes en el árbol de búsqueda binaria. En la siguiente línea, hay N enteros: un recorrido probabilístico de orden previo del árbol de búsqueda binaria. Todas las etiquetas de los Nodes en un caso de prueba serán distintas. El valor de cada etiqueta en un caso de prueba estará entre 1 y N, inclusive. Puede suponer que la entrada será un recorrido previo probabilístico válido de algún árbol de búsqueda binaria.
Producción
Para cada caso de prueba, imprima un solo número en una línea por sí mismo. Este número debe ser el número de diferentes recorridos probabilísticos de preorden que existen para el tee de búsqueda binaria, incluido el dado en el caso de prueba. Puede suponer que la respuesta siempre será menor o igual a 1,000,000,000. De hecho, es fácil ver que la respuesta nunca puede ser más de 2^30 (leído elevado).
Restricciones
1 < T <= 10000
1 <= N <= 30
Entrada de muestra
3
3
2 1 3
3
1 2 3
5
2 4 3 5 1
Salida de muestra
2
1
4
4) Se le proporciona una gran variedad de 10 000 000 bits. Cada bit es inicialmente 0. Realiza varias operaciones del tipo «Voltear todos los bits entre start_index y end_index, inclusive». Dada una secuencia de varias operaciones de este tipo, realice todas las operaciones en la array. Finalmente, divida la array en conjuntos de 4 bits: los cuatro primeros, los cuatro siguientes, los cuatro siguientes y así sucesivamente. Cada conjunto puede representar un entero hexadecimal. Habrá exactamente 2.500.000 enteros hexadecimales. Calcule la frecuencia de cada uno de los enteros hexadecimales desde ‘0’ hasta ‘f’ entre los 2.500.000 enteros e imprímala. Consulte Entrada/salida y la explicación de Entrada/salida de muestra para mayor claridad.
Aporte
La primera línea de entrada contiene un número entero T (1 ? T ? 10), el número de casos de prueba. Luego sigue la descripción de los casos de prueba T. Debe suponer que la array tiene exactamente 10 000 000 bits y que todos los bits están desactivados al comienzo de cada caso de prueba. La primera línea de cada caso de prueba contiene un número entero N (1 ? N ? 10 000), el número de operaciones realizadas. Las siguientes N líneas contienen dos números enteros separados por un espacio, el índice_inicial y el índice_final para la operación respectiva. Tenga en cuenta que la operación de volteo se realiza desde start_index hasta end_index, inclusive. Además, la array tiene un índice de 1, lo que significa que el índice más pequeño es 1 y el índice más grande es 10,000,000.
Producción
Para cada caso de prueba, genere 16 enteros en una sola línea, separados por caracteres de un solo espacio. El primer entero debe representar el número de veces que aparece 0 entre los 2.500.000 enteros hexadecimales creados de acuerdo con el enunciado del problema. El segundo entero debe representar el número de veces que aparece 1 entre los 2.500.000 enteros hexadecimales creados de acuerdo con el enunciado del problema, y así sucesivamente.
Restricciones
1 <= start_index <= end_index
start_index <= end_index <= 10,000,000
Entrada de muestra
2
2
1 4
9999997 10000000
2
3 6
5 8
Salida de muestra
2499998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
2499998 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0
5) Se le dan dos strings, digamos A y B, de la misma longitud, digamos N. Puede intercambiar A[i] y B[i] por todos los i entre 1 y N, inclusive. No puede intercambiar dos caracteres dentro de A o dentro de B. Además, solo puede intercambiar un carácter en A con el carácter en el mismo índice en B, y con ningún otro carácter. Puede realizar esta operación cero o más veces.
Desea modificar las strings a través de las operaciones de tal manera que la cantidad de caracteres únicos en las strings sea pequeña. De hecho, si n(A) es el número de caracteres únicos en A y n(B) es el número de caracteres únicos en B; desea realizar las operaciones de modo que max(n(A),n(B)) sea lo más pequeño posible.
Imprime el valor de max(n(A),n(B)) después de todas las operaciones.
Entrada
La primera línea de entrada contiene T, el número de casos de prueba. Luego sigue la descripción de los casos de prueba T. Cada caso de prueba contiene el número N en la primera línea. Las siguientes dos líneas del caso de prueba contienen dos strings de letras N, A y B respectivamente. Las letras son minúsculas en inglés.
Salida
Imprime una sola línea para cada caso de prueba. Imprima el valor de max(n(A),n(B)) después de realizar todas las operaciones de modo que el valor sea lo más pequeño posible.
Restricciones
1 <= T <= 100
1 <= longitud(A) <= 16
longitud(B) = longitud(A)
Entrada de muestra
3
7
directi
itcerid
5
ababa
babab
5
abaaa
baabb
Salida de muestra
4
1
2
6) Definamos una string como una etiqueta de apertura, donde x es cualquier letra pequeña del alfabeto latino.
Cada etiqueta de apertura coincide con una etiqueta de cierre del tipo, donde x es la misma letra.
Las etiquetas se pueden anidar entre sí, es decir, un par de etiquetas de apertura y cierre se pueden ubicar dentro de otro par.
Definamos la noción de un texto XML:
1) Una string vacía es un texto XML
2) Si S es un texto XML, entonces ” S ” (las comillas y los espacios son para mayor claridad) también es un texto XML,
donde a es cualquier letra latina minúscula
3) Si S1 , S2 son textos XML, luego «S1 S2» (las comillas y los espacios son para mayor claridad) también es un texto XML
Se le da una string. Debe verificar si la string dada es un xml válido o no.
Entrada La
primera línea contiene T número de casos de prueba
Para cada caso de prueba:
Solo una línea que contiene la string xml etiquetada S.
Salida
Imprimir en una línea una string VERDADERO si s es un xml válido FALSO si no lo es.
Restricciones
0 < T <= 10
0 < longitud de S <= 10^5 Entrada de
ejemplo : 2
Salida:
VERDADERO
FALSO
7) En este problema consideramos dos escaleras, A y B, que son paralelas entre sí. Ambas escaleras, A y B, tienen N escalones cada una, donde A[i], B[i] representan el i-ésimo escalón de A y B respectivamente.
Cada paso tiene una cantidad de penalización asociada y si usa ese paso, será penalizado por la misma cantidad. Después de dar algunos pasos, acumulará la penalización de todos los pasos que visitó.
Tiene una longitud de salto máxima de K, es decir, desde A[i] puede saltar hacia adelante a A[i+1] o A[i+2]… o A[i+K] sin usar ningún paso intermedio.
También puedes saltar las escaleras con una penalización adicional P por cambiar de escalera. Por ejemplo de A[i] puedes saltar a B[i+1] o B[i+2]… o B[i+K] con una penalización adicional P junto con la penalización del paso que visitas. También puede saltar de la escalera B a la escalera A y eso también incurre en una penalización adicional P junto con la penalización del escalón que visita.
Observa que de cada paso solo puedes saltar hacia adelante. Su penalización final será la penalización de todos los escalones que visitó más P por el número de veces que cruzó las escaleras.
Puedes empezar desde A[1] o B[1] y debes llegar a A[N] o B[N] minimizando la penalización acumulada en el camino. Halla la sanción mínima que acumularás.
Aporte
La primera línea en la entrada es igual a T, el número de casos de prueba. Luego sigue la descripción de los casos de prueba T. La primera línea en cada caso de prueba tiene tres números enteros N, el número de pasos en ambas escaleras, K, longitud máxima de salto, P, la penalización por cruzar las escaleras. En la segunda línea de cada caso de prueba, hay N enteros donde i-ésimo entero representa la penalización del paso A[i]. En la tercera línea de cada prueba, hay N enteros donde el i-ésimo entero representa la penalización del paso B[i].
Salida
Para cada caso de prueba, genere una sola línea que contenga la penalización mínima que puede acumular en su ruta comenzando desde { A[1] o B[1] } y terminando en { A[N] o B[N] }.
Restricciones
1 <= T <= 10
1 <= norte <= 1000
0 <= P <= 1000
1 <= K <= norte
0 <= A[i], B[i] <= 1000 Entrada de
ejemplo : 6 4 1 0 1 2 3 4 1 2 3 4 4 1 0 1 2 3 4 4 3 2 1 4 2 0 1 2 3 4 4 3 2 1 4 1 10 1 2 3 4 4 3 2 1 4 2 10 1 2 3 4 4 3 2 1 5 1 50 0 0 102 104 0 101 103 0 0 105
Salida:
10
6
4
10
7
100
8) En este problema consideramos un árbol con raíz Tr con raíz r (no necesariamente un árbol binario). A dfs – búsqueda primero en profundidad – recorrido del árbol Tr a partir de la raíz r, visita los Nodes de Tr en un orden particular. Llamemos a ese orden como ordenamiento dfs.
Observe que durante un recorrido de dfs, desde cada Node tenemos opciones entre qué niño recorrer primero.
Estas diferentes opciones conducen a diferentes órdenes de dfs. Debe encontrar diferentes formas en que un dfs puede visitar los Nodes, es decir, el número de ordenamientos diferentes de Nodes posibles por un dfs en Tr a partir de la raíz r.
Considere un ejemplo Tr con 3 Nodes etiquetados 1, 2, 3 con 1 como raíz y con 2 y 3 como hijos de 1.
Un dfs en este Tr puede visitar Nodes en el orden (1, 2, 3) o (1, 3, 2). Por lo tanto, hay 2 formas de ordenar dfs.
Ver ejemplos de casos de prueba para más ejemplos
Entrada
La primera línea en la entrada es igual a T, el número de casos de prueba. Luego sigue la descripción de los casos de prueba T. La primera línea en cada caso de prueba es el número entero N, el número de Nodes en el árbol Tr. Cada Node está etiquetado con un número entero distinto entre 1 y N inclusive. En la línea siguiente, hay N enteros donde i-ésimo entero representa la etiqueta principal del Node etiquetado como i en el árbol enraizado Tr. El valor de cada etiqueta en un caso de prueba estará entre 1 y N, inclusive. El Node principal del Node etiquetado como i tendrá una etiqueta menor que i. El Node con la etiqueta 1 es el Node raíz r. El Node padre del Node raíz se dará como 0 en los casos de prueba.
Producción
Para cada caso de prueba, genere una sola línea que contenga el número de ordenaciones diferentes posibles por dfs en Tree Tr. Dado que este número puede ser enorme, la salida del valor módulo 1,000,000,007.
Restricciones
1 <= T <= 100
1 <= N <= 1000
0 <= A[i] < i
Ejemplo
Entrada :
6
2
0 1
3
0 1 1
4
0 1 1 1
3
0 1 2
4
0 1 1 2
5
0 1 1 2 2
Salida :
1
2
6
1
2
4
9) Katrina es una súper friki. Le gusta optimizar las cosas. Supongamos que está en la posición (0,0) de una cuadrícula bidimensional que contiene ‘m’ filas y ‘n’ columnas. Ella quiere llegar al punto inferior derecho de esta cuadrícula viajando a través de la menor cantidad de celdas posible.
Cada celda de la cuadrícula contiene un número entero positivo, el número entero positivo define el número de celdas que Katrina puede saltar hacia la derecha o hacia abajo cuando llega a esa celda. No puede moverse hacia la izquierda o hacia arriba.
Debe encontrar la ruta óptima para Katrina para que, comenzando desde la posición superior izquierda de la cuadrícula, llegue a la posición inferior derecha en el número mínimo de saltos.
Aporte
Se le proporciona una plantilla en la que debe implementar una función minHops. La declaración de minHops parece
C / C++
int minHops(array int[64][64], int m, int n)
Java
statuc int minHops(int[][] array, int m, int n)
Salida
La función debe devolver la cantidad mínima de celdas que se deben tocar para llegar desde la esquina superior izquierda de la cuadrícula hasta la esquina inferior derecha (incluido tocar las celdas superior izquierda e inferior derecha). Devuelve 0 en caso de que no exista una ruta.
Ejemplo
Supongamos que la cuadrícula se ve así
2 4 2
5 3 8
1 1 1
Comenzar en A(0,0) contiene ‘2’, por lo que puede ir a (0,2) o (2,0).
Entonces, existen dos caminos para llegar a (2,2) desde (0,0)
(0,0) => (0,2) => (2,2)
(0,0) => (2,0) = > (2,1) => (2,2)
Por lo tanto, la salida para este caso de prueba debe ser 3
Ejemplo 2
5 3 8 2
6 4 2 1
No hay una ruta de (0,0) a (1,3), por lo que la salida para este caso debería ser 0
Ejemplo 3
2 3 2 1 4
3 2 5 8 2
1 1 2 2 1
Varios caminos en este caso son
(0,0) => (0,2) => (2,2) => (2,4)
(0,0) => (2,0) => (2,1 ) => (2,2) => (2,4)
Entonces, la salida, en este caso, debería ser 4
10) Considere la ciudad de Nueva York, que tiene una estructura de casas en forma de cuadrícula. Se le proporciona el mapa de la ciudad en forma de array. Cada celda representa un edificio. Desde cada edificio, puedes ir a los cuatro edificios adyacentes en cuatro direcciones: este, oeste, norte, sur. Spiderman quiere rescatar a una víctima que se encuentra en un edificio. Se le proporcionará la ubicación de la víctima y Spiderman se encuentra en el edificio (1,1). Pero, existe la condición de que Spiderman no pueda saltar entre edificios si la diferencia en sus alturas es mayor que algún valor particular. Encuentre una manera de que Spiderman alcance a la víctima cruzando la cantidad mínima de edificios.
Entrada
La entrada contiene varios casos de prueba. First Line es un entero T, que representa el número de casos de prueba a seguir.
La primera línea de cada caso de prueba tiene 4 números: M, N, X, Y, D. Aquí MxN es la dimensión de la cuadrícula de la ciudad. (X, Y) es la ubicación de la víctima.
Esto es seguido por líneas M. Cada línea consta de N números enteros positivos separados por espacios correspondientes a las alturas de los edificios. D es la diferencia máxima entre las alturas de los edificios que puede cruzar Spiderman.
Salida
Una línea para cada caso de prueba que contiene un solo número entero, que indica el número mínimo de edificios que Spiderman debe cruzar. Devuelve -1 si no es posible.
Restricciones
Debe contener todas las restricciones sobre los datos de entrada que pueda tener. Formatéelo como:
1 <= T, M, N, X, Y <= 100
1 <= D <= 100000 La
altura de cada edificio será inferior a 100000
Entrada de ejemplo :
3
3 3 3 3 2
1 2 3
6 9 4
7 8 5
3 3 3 3 1
1 8 3
9 5 6
7 2 4
3 3 3 3 1
1 6 7
2 5 8
3 4 9
Salida:
3
-1
7
11) Te dan un árbol de N Nodes. Cada uno de los Nodes estará numerado de 0 a N-1 y cada Node i está asociado a un valor vi.
Suponga que el árbol tiene su raíz en el Node 0.
Se dice que un Node y es descendiente del Node x si x se encuentra en la ruta del Node 0 al Node y. Un subárbol con raíz en el Node x se define como un conjunto de todos los Nodes que son descendientes de x (incluido x).
Un subárbol se llama sin valor si los valores de todos los Nodes en el subárbol son iguales.
Dado el árbol y los valores asociados con los Nodes en el árbol, debe encontrar la cantidad de subárboles sin valor en el árbol.
Aporte
La primera línea contiene un número entero N que es el número de Nodes en el árbol. Las siguientes N líneas contienen N enteros que representan los valores asociados con cada Node, es decir, la i-ésima línea contiene el valor asociado con el Node i-1. Las siguientes líneas N-1 dan la información de los bordes en el árbol. Cada línea contiene dos números enteros separados por espacios x e y que denotan un borde entre el Node x y el Node y.
Salida
Tiene que imprimir el número de subárboles sin valor que están contenidos en el árbol dado.
Restricciones
N<=30000
Ejemplo
Entrada:
5
0
0
1
1
1
0 1
0 2
2 3
2 4
Salida:
4
12) Directi organiza FNCS (Friday Night Chill Session) de vez en cuando (¡mucha DIVERSIÓN!). Los directores vienen y disfrutan de varios eventos y luego salen cuando se cansan y regresan cuando están descansados. Para mayor comodidad, se registra la entrada/salida de cualquier persona. Al final del día, el organizador se pregunta cuál fue el número máximo de personas durante el evento. Así que pide tu ayuda. Te da la hora de entrada y salida de cada persona así:
Person Entry_time Exit_time #1 6 10 #2 1 7 #3 1 4 #4 8 10 #5 6 10
No importa la identidad de la persona. #1 y #4 pueden ser la misma persona. En este caso, el número máximo de personas presentes durante el evento en cualquier momento es 3.
Su tarea es leer las entradas y calcular el número máximo de personas presentes durante el transcurso del evento.
Entrada
La entrada contiene varios casos de prueba. First Line es un entero T, que representa el número de casos de prueba a seguir. La primera línea de cada caso de prueba es un número N, número de registros de entrada y salida. Esto es seguido por N líneas. Cada línea consta de dos números enteros separados por espacios que corresponden a la hora de entrada y la hora de salida de una persona.
Salida
Una línea para cada caso de prueba que contiene un solo número entero, que indica el número máximo de personas presentes en la fiesta en cualquier momento.
Restricciones
1 <= T <= 100
1 <= N <= 100
1 <= ENTRY_TIME < EXIT_TIME <= 10000000
Se garantiza que la hora de entrada y salida de las personas sea distinta
Entrada de ejemplo :
1
6
7 8
4 9
6 9
8 17
2 14
2 10
Salida :
5
Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA