Un robot humanoide ha sido programado para caminar siguiendo una secuencia de pasos en un plano.
El robot comienza en la posición (0, 0). Los movimientos posibles son:
Avanzar un paso hacia arriba (incrementa y en 1).
Avanzar un paso hacia la izquierda (decrementa x en 1).
Avanzar un paso hacia la derecha (incrementa x en 1).
Avanzar un paso hacia abajo (decrementa y en 1). Al finalizar todos los pasos:
5FFLRF
Linea Recta
4FFRR
Derecha
8FRFRLLBL
Izquierda
Bob es un político que recientemente ha iniciado su campaña electoral para uno de los cargos más importantes del estado. Él quiere que su campaña sea lo más efectiva posible, por lo que ha decidido contratar a un equipo de expertos en marketing político para que lo ayuden a diseñar su estrategia de campaña. El equipo de expertos ha realizado un estudio exhaustivo y ha identificado las ciudades que tienen grupos de votantes similares y ha creado un mapa que muestra las interacciones entre ellas.
Con el propósito de comunicar sus discursos políticos y propuestas, Bob ha decidido iniciar un recorrido por las diferentes ciudades del estado. En la primera semana, Bob visitará una ciudad y comunicará su discurso y propuestas. En ese momento los votantes de dicha ciudad quedarán informados sobre las mismas y comenzarán a difundir la información con las ciudades vecinas. Sin embargo, les tomará una semana completar ese proceso. En la segunda semana, dos eventos simultáneos ocurren: Bob visitará otra ciudad para continuar su campaña, y, por el estudio realizado por su equipo, se sabe que los votantes de las ciudades previamente informadas ya habrán informado a sus ciudades vecinas, por lo que estas ya podrán ser consideradas informadas. El proceso se repetirá hasta que todas las ciudades queden informadas.
Bob y su equipo tienen dos posibles estrategias para visitar las ciudades. La primera estrategia consiste en visitar las ciudades impares de manera secuencial ascendente, y la segunda estrategia consiste en visitar las ciudades pares de manera secuencial ascendente. Además, dado que visitar dichas ciudades y dar los discursos suele ser muy costoso, a Bob y su equipo les gustaría visitar la menor cantidad de ciudades posibles, y que a su vez se logre que la información del discurso llegue a todas las ciudades y a sus votantes.
Considerando las dos estrategias mencionadas, ¿Cuántas semanas le tomará a Bob comunicar su discurso político?
Imagen ilustrativa (ChatGPT). La primera línea contiene dos enteros n y m (1 ≤ n ≤ 105,
), el número de ciudades y las relaciones de vecindad entre ellas, de acuerdo con el estudio realizado por el equipo de Bob. Las siguientes m líneas contienen dos enteros u y v (1 ≤ u, v ≤ n, u ≠ v), indicando que las ciudades u y v son vecinas. Las ciudades están numeradas del 1 al n.
Imprimir la cantidad mínima de semanas que le tomará a Bob comunicar su discurso político siguiendo alguna de las dos estrategias propuestas. En caso de que sea imposible que Bob pueda lograr su propósito, imprimir -1.
6 61 41 22 32 52 43 6
3
6 61 41 22 32 42 52 6
2
4 21 32 4
-1
Chatito es un gato muy inteligente que se toma las películas muy en serio. Un día, mientras analizaba la obra maestra Shrek, escuchó la famosa frase de Shrek a Burro:
"¡Los ogros son como las cebollas. Tienen capas!"
Chatito pausó la película. Sus ojos se abrieron de par en par. ¡Acababa de tener una revelación! ¡Las películas también tienen capas!
Él cree que el arco narrativo de un personaje no es una sola cosa, sino una secuencia de N "momentos". Ha medido la "vibra" de cada momento, dándote una lista de N números: A.
Su gran teoría es que la película está dividida en exactamente K "capas" (segmentos) emocionales. (Por ejemplo, la "capa de la ira", la "capa de la negación", la "capa de la amistad", etc.).
Chatito, en sus estudios de cine, ha identificado K "emociones puras". Cada emoción tiene un "puntaje de vibra perfecto" (un "target"). Estos son K números en una lista T.
Para que su reseña de 5 estrellas sea correcta, Chatito debe:
1. Partir la película (la secuencia A) en K segmentos contiguos.
2. A cada segmento, debe asignarle una de las K emociones puras.
¡No puede repetir emociones! Cada una de las K emociones debe usarse exactamente una vez.
Chatito necesita medir qué tan "mal" encaja una emoción en un segmento. A esto le llama el "costo de cringe". Lo calcula así:
donde;
a = Suma de la vibra del segmento
b = Vibra Perfecta de la Emocion
¡Ayuda a Chatito a encontrar la forma de partir la película que le dé el mínimo costo de cringe total!
La primera línea contiene dos enteros N y K (1 ≤ K ≤ 10; K ≤ N ≤ 100) — el número de 'momentos' en la película y el número de 'capas' emocionales.
La segunda línea contiene N enteros A1, A2, ..., AN (1 ≤ Ai ≤ 105) — la lista A de las 'vibras' de cada momento.
La tercera línea contiene K enteros T0, T1, ..., TK - 1 (1 ≤ Tp ≤ 107) — la lista T de las 'vibras perfectas' para cada una de las K emociones.
Imprime un solo número: el mínimo "costo de cringe" total que Chatito puede lograr.
2 25 1012 4
5
5 31 2 3 4 55 4 3
3
9 51 1 2 3 5 8 13 21 342 3 5 7 11
906
En el primer caso de ejemplo, la partición óptima es
.
- El segmento [5] se asigna a la 'vibra perfecta' 4.
- El segmento [10] se asigna a la 'vibra perfecta' 12.
El costo total es (5 - 4)2 + (10 - 12)2 = 12 + ( - 2)2 = 1 + 4 = 5. Se puede probar que este es el mínimo costo posible.
En el segundo caso de ejemplo, la partición óptima es
. La asignación óptima de vibras (5, 4, 3) es:
- El segmento [1, 2, 3] (Suma 6) -> 'vibra' 5. Costo: (6 - 5)2 = 1
- El segmento [4] (Suma 4) -> 'vibra' 3. Costo: (4 - 3)2 = 1
- El segmento [5] (Suma 5) -> 'vibra' 4. Costo: (5 - 4)2 = 1
El costo total es 1 + 1 + 1 = 3. Se puede probar que este es el mínimo costo posible.
¡Por fin! Estás a semanas de graduarte y solo te falta terminar tus residencias profesionales en TecNM Games, una compañía de creación de videojuegos muy famosa fundada por tus héroes de la programación competitiva y egresados del TecNM. Una vez graduado serás muy feliz, ¿verdad? ¡¿VERDAD?!
Bueno, que se preocupe de eso tu yo del futuro, ahorita hay que entregar tu proyecto final de la residencia, pero revisándolo, te has dado cuenta de que la dificultad del videojuego en el que trabajas puede ser mucho más baja de lo esperado tomando las rutas correctas.
En el videojuego, empiezas en el mundo 1 y, dependiendo de las rutas que tomes, te vas desplazando entre mundos hasta llegar al mundo final donde termina el juego. Ésto lo hace muy divertido, porque puedes jugarlo una y otra vez, posiblemente descubriendo nuevos mundos cada vez.
Sin embargo, tu preocupación es que haya una secuencia de mundos que sea tan fácil de que lo detecten los jugadores, que se haga viral y ya todos puedan fácilmente decir que vencieron a tu juego. Para ello, quieres analizar cuál es dicha secuencia y mostrárselo al encargado del proyecto, para ver si lo dejan así o le suben el nivel de dificultad.
Para saber la dificultad de una ruta, cada mundo tiene un nivel de dificultad diferente que se debe multiplicar con los demás de la ruta, mientras más grande sea este número más difícil la ruta es.
Por detalles técnicos del juego, la dificultad de cada mundo es un número primo diferente, el cual también se utiliza como su identificador. Además, por diseño, el mundo inicial siempre es el 1, y el mundo final es el que tiene el identificador mayor.
En la primera línea encontrarás un número M, que determina el número de pares de mundos que están unidos en el videojuego.
En las siguientes M líneas, habrá dos enteros a y b, indicando que hay una manera de desplazarse del mundo a al b.
En una sola línea, deberás indicar los identificadores de los mundos a visitar del mundo inicial al final, de tal manera que la ruta tenga la menor dificultad posible. Imprime los identificadores separados por un espacio en el orden a visitar.
Se garantiza que exista al menos una ruta y, en caso de haber varias rutas con la misma dificultad, deberás escoger la primera lexicográficamente para evitar ambigüedades.
61 22 33 55 77 1111 13
1 2 3 5 7 11 13
53 73 51 35 137 13
1 3 5 13
1 ≤ M ≤ 106
1 ≤ a, b ≤ 106
a ≠ b
a y b son primos
Tu maestra de programación es una amante del abecedario, piensa que el abecedario debería ser infinito, pero lastimosamente no lo es. Sin embargo, a ella le gusta jugar a que sí, y para lograrlo simplemente agrega un número antes de la letra, que representa el número de apariciones que tiene esa letra anteriormente en "el abecedario infinito" y repite las letras en el orden conocido.
Para que quede más claro, este es un ejemplo de cómo se verían los primeros valores de su intento de "abecedario infinito":
0a, 0b, 0c, 0d, 0e, 0f, 0g, 0h, 0i, 0j, 0k, 0l, 0m, 0n, 0o, 0p, 0q, 0r, 0s, 0t, 0u, 0v, 0w, 0x, 0y, 0z, 1a, 1b, 1c, 1d, 1e, 1f, 1g, 1h, 1i, 1j, 1k, 1l, 1m, 1n, 1o, 1p, 1q, 1r, 1s, 1t, 1u, 1v, 1w, 1x, 1y, 1z, 2a, 2b, 2c, 2d, 2e, 2f, 2g, 2h, 2i, 2j, 2k, 2l, 2m, 2n, 2o, 2p, 2q, 2r, 2s, 2t, 2u, 2v, 2w, 2x, 2y, 2z, 3a, 3b, 3c, 3d, 3e, 3f, 3g, 3h, 3i, 3j, 3k, 3l, 3m, 3n, 3o, 3p, 3q, 3r, 3s, 3t, 3u, 3v, 3w, 3x, 3y, 3z, 4a, 4b, 4c, 4d, 4e, 4f, 4g, 4h, 4i, 4j, 4k, 4l, 4m, 4n, 4o, 4p, ...
Como se puede notar, la posición 1 de este "abecedario infinito" es "0a", la posición 2 es "0b", y así sucesivamente.
Tu maestra, además de ser una amante del abecedario, también lo es de las sucesiones numéricas. Ella confía en que tú también lo seas, pues te trae un problema que combina sus dos pasiones: sucesiones numéricas y su "abecedario infinito".
Ella ha elegido una sucesión numérica, y de dicha sucesión fue seleccionando en orden esas posiciones de su abecedario, para que en lugar de mostrar el número que sigue en su sucesión, mostrar el valor de su abecedario que está en la posición con ese número.
Es decir, si en su sucesión numérica está un 6, ella pondría en su lugar, el valor ¨0f¨, que es el que esta en abecedarioInf[6] (indexado en 1). Si su sucesión numérica fuera [2, 4, 6, 8]. Entonces, su nueva sucesión no numérica sería [abecedarioInf[2], abecedarioInf[4], abecedarioInf[6], abecedarioInf[8]]. O sea: [0b, 0d, 0f, 0h].
La sucesión infinita que ella creó, llamémosle s, mezclando sus pasiones inicia así:
0e, 0h, 0m, 0t, 1c, 1n, 2a, 2p, 3g, 3z, 4u, 5r, 6q, 7r, 8u, 9z, 11g, 12p, 14a, ...
Ahora que ya sabes la sucesión s que tu maestra ha creado. Ella quiere retarte a que dado un valor c de su abecedario infinito, le digas en qué posiciones de su s está (indexado en 1), si es que pertenece a dicha sucesión. Si no, imprime -1.
Una cadena c que representa un valor válido del abecedario infinito que inventó tu maestra. Donde c se conforma por un prefijo numérico 0 ≤ p ≤ 100000000 seguido de una letra del abecedario ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'].
Imprime un entero x que represente la posición de la sucesión s en la que se encuentra dicha cadena c, si es que sí aparece en ella.
Imprime -1 si la cadena c no pertenece a la sucesión que formó tu maestra.
0e
1
3z
10
104d
52
0d
-1
Según la mitología azteca, el camino al inframundo, Mictlán, es un arduo viaje de nueve niveles. Antonia ha llegado a uno de estos laberintos, un lugar donde las almas de los difuntos son guiadas por las corrientes del viento, que soplan en una de cuatro direcciones: arriba (^), abajo (v), izquierda (<) o derecha (>).
El laberinto es una cuadrícula de R × C celdas. Para llegar a su destino, Antonia debe ir de la celda de entrada (0, 0) a la celda de salida (R−1, C−1).
Moverse a través del laberinto tiene un costo de energía. Si se mueve a una celda adyacente (arriba, abajo, izquierda, o derecha) a favor de la corriente del viento de la celda actual, el costo es 0. ¡El viento la empuja! Si se mueve a una celda adyacente en contra de la corriente del viento, el costo es 1. ¡Debe usar su propia fuerza para avanzar!
La misión de Antonia es encontrar el mínimo costo de energía para llegar del punto de partida al punto final, ayuda a Antonia en esta díficil misión.
La primera línea contiene dos enteros R y C (1 ≤ R, C ≤ 500), las dimensiones de la cuadrícula. Las siguientes R líneas contienen una cadena de C caracteres, cada uno representando la dirección del viento (^, v, <, >).
Un solo entero, el mínimo costo de energía necesaria para ir de inicio a fin.
4 5>>>><^v>><^<>v><v>><
2
2 2<>^v
2
Las Tortuguitas
En la costa michoacana cada año arriban miles de tortugas las cuales hacen hoyos en la arena de la playa para depositar sus huevos, de los cuales, tiempo después nacen decenas de tortuguitas bebes.
Es un gran espectáculo de ver emerger decenas de tortuguitas de entre la arena. Es asombroso y tu quieres presenciar la mayor cantidad posible de estos. 
Imaginate que estás de visita en la costa michoacana tratando de presenciar el mayor número de nacimientos posibles para lo cual debes correr de un nido a otro mientras emergen.
Este problema trata de encontrar el mayor número de nacimientos posibles que puedes presenciar tomando en cuenta que tu posición inicial es cero y el tiempo inicial es cero.
Solo puedes ver el nacimiento de las tortugas del nido i-esimo si estas en la posicion Xi del nido en exactamente el tiempo Ti en que los huevos eclosionan de este nido.
Puedes moverte a velocidad 1 (una posición por unidad de tiempo) o esperar una unidad de tiempo en la posicion en la que te encuentras.
La primera linea contiene un entero N (1 ≤ N ≤ 103) indicando la cantidad de nidos de tortugas.
Le siguen N líneas, donde la linea i contiene la posición Xi ( - 109 ≤ Xi ≤ 109) del nido i, y el tiempo Ti (0 ≤ Ti ≤ 109) en que emergen las tortuguitas de ese nido.
Un único valor indicando el mayor número de nidos que puedes a visitar.
(20 puntos): se cumple que N, abs(Xi), Ti < = 20.
(80 puntos): los limites originales
21 12 2
2
4-8 81 89 3-2 1
1
Resulta que la vida laboral es justo como la escuela, pero aún peor. Ahora en lugar de conectar routers en un salón de clase tu trabajo es conectar un montón de routers repartidos a través de una ciudad con calles perféctamente cuadradas. Para ello tienes que conectarlos con fibra óptica a través de postes y vías subterráneas; para propósitos prácticos supongamos que no importa por dónde los metas entre esas dos, pero lo importante es que no los metas a través de manzanas. Para tu conveniencia los routers siempre estarán en las esquinas de las manzanas.
Igual que en la escuela, lo importante es pasar. En este caso eso significa solo conectar los routers; redundancia y cosas por el estilo no importan.
Un número N, el número de routers a conectar.
En las siguientes N líneas, N pares de números xi, yi representando cada una de las coordenadas de los routers.
La mínima longitud de cable necesaria para conectar todos los routers.
3 5 7 1 1 2 8
12
Se puede conectar el router en la posición (1, 1) con el de la posición (2,8); estos están a distancia 8. Luego conectamos el (2, 8) con el (5, 7), y estos 2 están a dsitancia 4. La distancia total es 8 + 4 = 12.
Benito es un amante de la aventura y la ciencia. Un día mientras caminaba en el reino de Elfrieden intentando encontrar una ruta más corta hacia la biblioteca descubrío una cueva repleta de cristales mágicos.
Ahí conoció a un mago-investigadora llamada Ichi que le hablo sobre estos. Ichi explico que ha estado estudiando estos cristales por mucho tiempo y ha descubierto que tienen distintos poderes y fortalezas. Por lo que las clasifico en lo que el llamo familias. Cada familia tiene un color único y con distinto poder, el lo llamo chispa mágica. Como el nombre de los cristales estan escrito en un alfabeto distinto, Ichi se dio a la tarea de convertir el alfabeto inglés por simplicidad, pero nota que tiene una diferencia ya que su alfabeto tiene mas letras por lo que después de la traducción las mayúsculas y minúsculas tienen un significado distinto. Además de que este no utiliza los números para los nombres.
Ichi te comentó que quiere hacer más experimentos pero debido a sus responsabilidades no tiene mucho tiempo libre. El quiere probar una teoría sobre la resistencia y poder de los cristales. Por lo que quiere tu ayuda para realizar un experimento muy particular. Te da la tarea de que lo ayudes a escoger cristales para el experimento. Pero hay una regla importante que debes seguir: Solo elegir un cristal de cada familia, es decir, no puedes elegir dos cristales del mismo color.
La meta es elegir K cristales que cuando se unan nos den el poder más grande posible.
Benito ha hecho un reporte con todos los cristales que existen en la cueva. Pero esto lo dejó sin energía. Por eso te pide que lo ayudes a encontrar los cristales que necesita.
La primer línea contiene dos números N y K. Estos representan el total de cristales mágicos que existen en la cueva (3 ≤ N ≤ 106) y el número de cristales que Ichi necesita para su experimento (1 ≤ K ≤ N) respectivamente.
La siguiente línea contiene dos valores Ci y Pi. Ci es una cadena (1 ≤ |Ci| ≤ 1000) que representa el nombre de la familia y Pi un entero (1 ≤ Pi ≤ 109) que representa el poder de dicho cristal.
Por cada caso se deberán imprimir lo siguiente: En la primer línea el poder que tienen todos los cristales seleccionados unidos. En caso que no sea posible elegir cristales que cumplan las restricciones, imprimir la palabra "IMPOSIBLE". Si existe una solución, entonces en la segunda línea, una lista con los indices ordenados de los cristales que fueron seleccionados. Si existen multiples soluciones, entonces imprimir la que sea lexicrográficamente menor.
5 3ROJO 5AZUL 3ROJO 4VERDE 6AZUL 2
14 1 2 4
4 3AMARILLO 4GRIS 5AMARILLO 6GRIS 7
IMPOSIBLE
En el caso dos, solo hay 2 colores distintos por lo que la salida es "IMPOSIBLE"
En la zona sur de Guanajuato se encuentran Uriangato y Moroleón, ambas ciudades se dedican principalmente a la producción y venta de productos textiles, existen tanto fábricas de gran tamaño como pequeños talleres que fabrican no solo para los alrededores, sino que atienden pedidos para todo el país.
La fábrica Productora Textil ha comenzado como un pequeño taller y al paso de los años ha ido creciendo, al grado de que se le hace cada vez más complicado manejar los pedidos que llegan, teniendo en ocasiones que pagar grandes penalizaciones por incumplimiento en la entrega. El trabajador Espino Espinoza es el responsable de recibir y dar seguimiento a la producción de los pedidos, además Espino tiene muchas otras responsabilidades en la fábrica y no le gusta delegar porque es muy obsesivo con su trabajo. Después de una ardua labor de convencimiento del departamento de calidad, se ha logrado convencer a Espino de que necesita una herramienta que le ayude a calendarizar, así podría hasta visualizar la producción de varios meses.
Cuando Espino recibe un pedido, siempre debe identificar la fecha en la que se está recibiendo, la fecha de entrega, cantidad a entregar y un monto diario de multa por incumplimiento en la entrega de acuerdo a lo convenido con el cliente.
Espino necesita que le ayudes a generar una simulación con los pedidos considerando lo siguiente:
Afortunadamente, la fábrica tiene una buena gestión interna de procesos y tiene una capacidad instalada bastante acertada, misma que por día pudiera ser distinta, ya que dependiendo de la época del año suelen reducirse los trabajadores y los turnos o por el contrario incrementarse.
Una primera línea contendrá la capacidad instalada CI para cada día de la semana iniciando con el lunes.
En seguida un número desconocido de líneas (una para cada pedido recibido), la información de cada pedido será la siguiente: la fecha de recepción del pedido FR, la fecha de entrega esperada FE, la cantidad de unidades solicitadas U y finalmente, la penalización diaria por entrega tardía P.
Espino delimitará el ingreso de pedidos con el símbolo #
Una línea con el cálculo de la penalización final acumulada de acuerdo a los pedidos. Seguida por una línea para cada pedido tal como está propuesto ingresarlos a producción, la información requerida para cada pedido deberá separarse por un espacio y será la siguiente:
1000 1000 1000 1000 1000 1000 021-09-2025 04-10-2025 2000 500023-09-2025 01-10-2025 1500 200021-09-2025 30-09-2025 10000 1000024-09-2025 05-10-2025 100 100#
58300 C 21-09-2025 30-09-2025 22-09-2025 02-10-2025 30000 B 23-09-2025 01-10-2025 03-10-2025 04-10-2025 8000 A 21-09-2025 04-10-2025 04-10-2025 07-10-2025 20000 D 24-09-2025 05-10-2025 07-10-2025 07-10-2025 300
1500 1500 1500 1500 1500 500 021-09-2025 04-10-2025 2000 500023-09-2025 01-10-2025 3500 200021-09-2025 30-09-2025 9000 1000024-09-2025 05-10-2025 1200 100#
2000 C 21-09-2025 30-09-2025 22-09-2025 29-09-2025 0 B 23-09-2025 01-10-2025 29-09-2025 01-10-2025 2000 A 21-09-2025 04-10-2025 02-10-2025 03-10-2025 0 D 24-09-2025 05-10-2025 03-10-2025 04-10-2025 0
0 ≤ CI ≤ 104
1 ≤ U ≤ 106
1 ≤ P ≤ 105
El formato de las fechas será dd - mm - aaaa
Tú y tus amigos cinéfilos están muy emocionados después de ver la ceremonia de los premios Óscar. Decidieron crear un reto de películas para este año: tomarán una lista de películas que ninguno haya visto antes y, a partir de ella, organizarán un maratón cinematográfico para las vacaciones.
Sin embargo, no pueden elegir las películas de cualquier manera. El maratón debe cumplir las siguientes condiciones:
1. El maratón debe avanzar a través del tiempo: cada película seleccionada debe tener un año de estreno mayor o igual al de la película anterior.
2. El maratón debe ser variado: no deben incluirse dos películas del mismo director de manera consecutiva.
3. Cada película seleccionada debe ser "mejor" que la anterior, donde "mejor" se mide usando el puntaje dado (por ejemplo, de IMDb o Rotten Tomatoes).
Dada la lista de películas, tu tarea es determinar la mayor cantidad de películas que tú y tus amigos pueden ver en este maratón.
La primera linea de entrada consistirás de un numero N(1 < = N < = 3 * 103), que representa la cantidad de películas a escoger. Cada una de las siguientes N lineas representara una película, cada película esta definida por su año de estreno Y(1820 < = Y < = 2050), el nombre del director (Un único nombre de hasta 50 letras, sin apellidos, que se compone únicamente de dígitos, letras mayúsculas y minúsculas del alfabeto inglés), y su puntaje P(0 < = P < = 100).
La maxima cantidad de películas que pueden ver en el maratón, dadas las condiciones previamente definidas.
62001 Nolan10 602004 Miyazaki 652002 Coppola 551999 Tarantino 502003 Cuaron 702005 Jeunet 80
4