Experiencia Entrevista Directi | Serie 19 (Preguntas de la Ronda 1)

PREGUNTAS 1) Declaración del problema
Usted está en un negocio de logística de alimentos. Tienes N jarras, cada una con capacidad ilimitada. Inicialmente, cada jarra contiene exactamente 1 litro de jugo. Desea llevar estas jarras a un lugar de entrega, pero solo puede llevar K jarras a la vez. No quiere desperdiciar jugo y no quiere hacer más de un viaje, por lo que decide redistribuir el contenido de las jarras hasta que no tenga más de K jarras no vacías.

Solo se le permite redistribuir el jugo usando el siguiente método. Primero, elija dos jarras que contengan la misma cantidad de jugo. Luego, vierte todo el contenido de una de esas jarras en la otra. Repite este proceso tantas veces como sea necesario.

Debido a esta restricción, puede ser imposible terminar con no más de K jarras no vacías usando solo las N jarras que tiene inicialmente. Afortunadamente, también puedes comprar más jarras. Cada jarra que compre contendrá exactamente 1 litro de jugo y tendrá capacidad ilimitada. Por ejemplo, considere el caso donde N es 3 y K es 1. Es imposible pasar de 3 jarras a 1. Si vierte una jarra en otra, termina con una jarra de 2 litros y una jarra de 1 litro. En ese punto, estás atascado. Sin embargo, si luego compra otra jarra, puede verter esa jarra en la jarra de 1 litro y verter la jarra resultante de 2 litros en la otra jarra de 2 litros para terminar con una sola jarra de 4 litros.

Devuelve la cantidad mínima de jarras adicionales que debes comprar para lograr tu objetivo. Si es imposible, devuelva -1 en su lugar.

Restricciones

– N estará entre 1 y 10^7, ambos inclusive.

– K estará entre 1 y 1000, ambos inclusive.
Ejemplos
1)
Entrada
3
1
Salida
1
(El ejemplo del enunciado del problema).
2)
Entrada
13
2
Salida
3
(Si tiene 13, 14 o 15 jarras, no puede terminar con una o dos jarras. Con 16 jarras, puede terminar con una jarra.)
3)
Entrada
1000000
5
Salida
15808

PREGUNTAS 2)
Descripción del problema: Rahul acaba de salir de la escuela y está ingresando a la universidad. Con suerte, tiene la opción de estudiar en 2 cursos en la universidad. A y B son los nombres de los cursos, que son iguales en cuanto a la duración del curso. Tanto A como B tienen N subcursos cada uno donde A[i], B[i] representan el i-ésimo subcurso de A y B respectivamente.

Cada subcurso tiene una cantidad de tarifa asociada y si estudias ese subcurso tendrás que pagar esa misma cantidad. Después de tomar algunos subcursos, acumulará la tarifa de todos los subcursos que estudió.

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 estudiar ningún subcurso intermedio en orden. para reducir su tarifa.

También puede saltar a través de los recorridos A y B con una penalización adicional P por cambiar de recorrido. Por ejemplo, de A[i] puedes cambiar a B[i+1] o B[i+2]… o B[i+K] con una penalización adicional P junto con la tarifa del subcurso que estudias. También puede saltar del curso B al curso A y eso también incurre en una penalización adicional P junto con la tarifa del subcurso que estudia.

Observa que desde cada subcurso solo puedes saltar hacia adelante. Su tarifa final será la tarifa de todos los subcursos que estudió más P multiplicado por la cantidad de veces que cambió de curso.

Puede comenzar desde A[1] o B[1] y debe llegar a A[N] o B[N] minimizando la tarifa acumulada en el camino. Encuentra la tarifa mínima que acumularás.

Entrada
La primera línea de 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 subcursos en ambos cursos, K, longitud máxima de salto, P, penalización por cambiar de curso. En la segunda línea de cada caso de prueba hay N números enteros donde el i-ésimo número representa la tarifa del subcurso A[i]. En la tercera línea de cada prueba hay N números enteros donde i-ésimo número representa la tarifa del subcurso B[i].

Salida
Para cada caso de prueba, genere una sola línea que contenga la tarifa mínima que puede acumular en su ruta de estudio comenzando desde { A[1] o B[1] } y terminando en { A[N] o B[N] }.

Restricciones
1 <= T <= 10
1 <= N <= 1000
0 <= P <= 1000
1 <= K <= N
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
Explicación
Ejemplo de caso de prueba 1.

Ambos cursos son iguales y la longitud del salto es 1, por lo que debe visitar todos los subcursos en un solo curso

Ruta mínima: A[1], A[2], A[3], A[4]

Por lo tanto, la respuesta es 10 para el primer caso de prueba.

Ejemplo de caso de prueba 2.

A tiene valores menores inicialmente y luego B tiene valores menores más tarde. Entonces, comenzar desde A y saltar a B sería óptimo

Ruta mínima: A[1], A[2], B[3], B[4]

Por lo tanto, la respuesta es 6 para el segundo caso de prueba.

Ejemplo de caso de prueba 3.

Ruta mínima: A[1], B[3], B[4]

Por lo tanto, la respuesta es 4 para el tercer caso de prueba.

Ejemplo de caso de prueba 4.

Ruta mínima: A[1], A[2], A[3], A[4]

No cambiaremos de curso porque la penalización por cambiar es muy alta. Por lo tanto, la respuesta es 10 para el cuarto caso de prueba.

Ejemplo de caso de prueba 5.

Ruta mínima: A[1], A[2], A[4]

Por lo tanto, la respuesta es 7 para el quinto caso de prueba.

Ejemplo de caso de prueba 6.

Ruta mínima: A[1], A[2], B[3], B[4], A[6]

Por lo tanto, la respuesta es 100 para el sexto caso de prueba. Tenga en cuenta cómo el caso óptimo podría requerir que cambie los cursos varias veces.

¡MIS MEJORES DESEOS! 🙂

Este artículo es una contribución de Phalguni Rathod . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo 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.