Entrevista Directa | Conjunto 9 (en el campus)

Toma el tren
Estás caminando por las escaleras mecánicas para tomar un tren subterráneo. La propia escalera mecánica se mueve a una velocidad de Ve metros por minuto. Puedes bajar por la escalera mecánica a una velocidad relativa de Vy metros por minuto. La longitud de la escalera mecánica es de L metros. Los trenes llegan con T minutos de diferencia. Sea t el tiempo entre tu llegada a la estación si te quedas parado en la escalera mecánica y la llegada del último tren antes de tu llegada. Suponga que t es una variable aleatoria distribuida uniformemente entre 0 y T. Devuelva la probabilidad de tomar un tren anterior si elige caminar por las escaleras mecánicas en lugar de quedarse quieto en ellas.

Entrada:
la primera línea de la entrada contiene un número entero Tc que indica el número de casos de prueba.
Cada caso de prueba contiene las siguientes 4 líneas

Ve – velocidad de la escalera mecánica

Vy – tu velocidad relativa con la escalera mecánica

L – longitud de la escalera mecánica

T – Período de tiempo de
salida de trenes
Para cada caso de prueba, genere una sola línea que contenga la probabilidad esperada de tener un error absoluto o relativo menor que 10^-6.

Restricciones
0 <= Tc <= 5 * 10 ^ 7
1 <= Ve <= 1000
1 <= Vy <= 1000
1 <= L <= 10 ^ 5
1 <= T <= 10 ^ 6

Entrada de ejemplo :
2
10
10
20
2
10
10
100
4

Salida:
0.5
1.0

Explicación
Caso de ejemplo 1. Si te quedas quieto, tardarás 20/10 = 2 minutos en llegar al pie de la escalera mecánica. Si elige caminar, obtendrá 20/(10+10) = 1 minuto. En el segundo caso te ahorras 1 minuto y en el 50% de los casos te permitirá coger un tren más temprano.

Caso de ejemplo 2. Aquí, si elige caminar en lugar de quedarse quieto, ahorrará 5 minutos y ciertamente tendrá la garantía de tomar un tren más temprano.

Cajas de caramelos
Tienes N paquetes de caramelos, cada uno con un número diferente de caramelos. El número de caramelos contenidos en el i-ésimo paquete se indica mediante ci. Debe colocar estos paquetes de caramelos en M cajas de modo que cada caja contenga al menos un paquete de caramelos y la cantidad máxima de caramelos en una caja sea mínima.
Solo puede elegir paquetes de caramelo consecutivos para poner en una caja.

Entrada
La primera línea de la entrada contiene un número entero T que denota el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos números enteros N, M separados por espacios que indican el número de paquetes de caramelo y el número de cajas, respectivamente. La segunda línea de cada caso de prueba contiene N enteros separados por espacios c1, c2, …, cN donde ci indica el número de toffees en el i-ésimo paquete de toffees.

Salida
Para cada caso de prueba, genere una sola línea que contenga el número máximo de toffees en una caja. Además, genere -1 si tal asignación de paquetes de toffee a cajas no es posible.

Restricciones
1 <= T <= 20
1 <= N,K <= 100000
1 <= ci <= 1000

Entrada de ejemplo :
1
4 2
10 3 5 7

Salida:
13

Explicación
A continuación se muestran las posibles asignaciones de paquetes de caramelo a cajas.
1. 10 [3 5 7]
2. 10 3 [5 7]
3. 10 3 5 [7]
Para minimizar el número máximo de caramelos en una caja, elegimos la segunda asignación y, por lo tanto, la salida debe ser 13

Guess Your Way Out
Amr compró un nuevo videojuego “Guess Your Way Out!”. El objetivo del juego es encontrar una salida del laberinto que parezca un árbol binario perfecto de altura h. El jugador está inicialmente parado en la raíz del árbol y la salida del árbol se encuentra en algún Node de hoja.
Indexemos todos los Nodes hoja de izquierda a derecha de 1 a 2^h. La salida está ubicada en algún Node n donde 1 <= n <= 2^h, el jugador no sabe dónde está la salida, ¡así que tiene que adivinar la salida!
Amr sigue un algoritmo simple para elegir el camino. Consideremos la string de comando infinita «LRLRLRLRL…» (que consta de caracteres alternos ‘L’ y ‘R’). Amr ejecuta secuencialmente los caracteres de la string usando las siguientes reglas:
1. El carácter ‘L’ significa «ir al hijo izquierdo del Node actual»;
2. El carácter ‘R’ significa «ir al hijo derecho del Node actual»;
3. Si ya se visitó el Node de destino, Amr omite el comando actual; de lo contrario, se mueve al Node de destino;
4. Si Amr omitió dos comandos consecutivos, vuelve al padre del Node actual
5. antes de ejecutar el siguiente comando;
6. Si llegó a un Node hoja que no es la salida, regresa al padre del
Node actual;
7. Si llega a una salida, el juego termina.
Ahora Amr se pregunta, si sigue este algoritmo, ¿cuántos Nodes visitará antes de llegar a la salida?
La primera línea de entrada
contiene T el número de casos de prueba
Las siguientes T líneas contienen 2 enteros h,n

Salida
T líneas de salida, cada una de las cuales contiene un número entero que representa el número de Nodes (excluyendo el Node de salida) que Amr visitará antes de llegar a la salida siguiendo este algoritmo.

Restricciones
1 <= T <= 10
1 <= h <= 50
1 <= n <= 2^h Entrada de ejemplo: 1 2 2 Salida: 2 Explicación Caso de ejemplo 1. Amr visitaría primero el Node raíz y luego raíz->Node izquierdo y luego vaya al Node raíz->izquierda->derecha que es la salida. por lo tanto, 2 Nodes visitados antes de llegar a la salida

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.