Fundamentos de Programación 1 Grupo DG - Facultad de Informática - UCM
Profesora: Isabel Pita
Problemas propuestos de Acepta el reto para la asignatura de Fundamentos de programación 1 de los alumnos del doble grado en Matemáticas e Informática
Resumen de los problemas enviados a Acepta el reto
Aquí puedes ver el resumen/resultado de todos los envíos realizados durante el primer cuatrimestre de FP1 del curso 2024-2025 por los alumnos del doble grado en Matemáticas e Informática de la Facultad de Informática de la UCM.
El cuatrimestre está dividido en distintos periodos de tiempo no necesariamente iguales pues se corresponden más con secciones temáticas que con semanas o quincenas.
Cada periodo tiene su propia pestaña donde se ven los detalles (entre ellos el intervalo de fechas correspondiente a ese periodo y los problemas aconsejados en él).
Para cada periodo se muestra una clasificación con los usuarios que han resuelto más ejercicios (y en caso de empate, en menos tiempo). En la lista sólo aparecen los envíos realizados por alumnos del grupo del doble grado en Matemáticas e Ingeniería Informática. Para poder aparecer en la lista de alumnos debes enviar el identificador de tu usuario del juez aceptaelreto a la profesora mediante la encuesta que se encuentra en el campus virtual en la pestaña General. En la encuesta se explica como obtener dicho identificador en la página de aceptaelreto.
Clasificación general
La tabla que aparece a continuación condensa el número total de problemas resueltos de cada periodo por cada usuario.
Problemas para empezar a conocer el juez. Todos ellos se resuelven mediante expresiones o un bucle for sencillo.
Hay alguno en que la parte más difícil es descubrir cómo resolverlos con lápiz y papel, no cómo escribirlo en C++.
Problemas que se resuelven con expresiones y con instrucciones condicionales. En algunos hace falta formatear la salida, fijate bien como se debe escribir el resultado. Recuerda los manipuladores std::setw(n) y std::setfill(c) de la librería iomanip. Para leer una hora de la entrada, debes leer primero un valor entero que corresponde con las horas, luego un carácter para leer los dos puntos, luego otro entero para leer los minutos etc. Para ello declara una variable de tipo char y utilízala para leer los dos puntos cuando corresponda.
Fíjate en el tipo de entrada que tiene el problema y utiliza la plantilla adecuada para cada caso. Puede ser por número de casos, por centinela o por casos ilimitados. Las plantillas las puedes encontrar en el campus virtual. En la plantilla por casos ilimitados fíjate que se debe realizar la lectura de un dato antes de preguntar si cin está en modo fallo.
Problemas que se resuelven con expresiones, instrucciones condicionales y bucles sencillos.
Fíjate en el tipo de entrada que tiene el problema y utiliza la plantilla adecuada para cada caso. Puede ser por número de casos, por centinela o por casos ilimitados. Las plantillas las puedes encontrar en el campus virtual.
Algunos de estos problemas ya empiezan a complicarse. Se puede necesitar algún bucle anidado (un bucle dentro de otro bucle)
Fíjate en el tipo de entrada que tiene el problema y utiliza la plantilla adecuada para cada caso. Puede ser por número de casos, por centinela o por casos ilimitados. Las plantillas las puedes encontrar en el campus virtual.
Algunos de estos problemas pueden necesitar el algoritmo del cálculo del m.c.d. (visto en un problema del juez), o bucles anidados (un bucle dentro de otro bucle)
Fíjate en el tipo de entrada que tiene el problema y utiliza la plantilla adecuada para cada caso. Puede ser por número de casos, por centinela o por casos ilimitados. Las plantillas las puedes encontrar en el campus virtual.
En algunos de estos problemas es necesario guardar todos los datos de entrada para después ordenarlos. Para guardar colecciones de valores del mismo tipo se utilizan una variable de tipo array. Para declarar la variable debéis indicar el tipo de los valores que va a guardar (todos los valores que guarda tienen que ser del mismo tipo), a continuación el nombre de la variable y entre corchetes el tamaño. El tamaño debe ser fijo y estar definido en una constante de tipo entero. Para saber que tamaño debes darle al array mira la descripción de la entrada en el enunciado del problema.
Para acceder a cada componente del array se utiliza su posición. La primera posición es la cero. Por lo tanto la última será el número de valores que guarda menos uno. Por ejemplo, el siguiente código declara un array, lee los valores del teclado y calcula su suma.
const int MAX = 1000;
void resuelveCaso()
...int numElem; std::cin >> numElem;
...int array[MAX];
...... for (int i = 0; i < numElem; ++i)
...... std::cin >> array[i];
... int suma = 0;
... for (int i = 0; i < numElem; ++i)
...... suma += array[i];
... std::cout << suma;
Para ordenar los datos de un array debéis utilizar la función sort de la librería algorithm. Cómo estamos utilizando arrays y no vectores, la instrucción adecuada es: std::sort(v,v+TAM); siendo v el array y TAM el número de elementos del array. La instrucción ordena los valores en orden creciente desde el cero hasta TAM.
Para otros tipos de ordenación consultar las transparencias de clase.
En algunos de estos problemas es necesario guardar todos los datos de entrada para después ordenarlos. Para guardar colecciones de valores del mismo tipo se utilizan una variable de tipo array. Para declarar la variable debéis indicar el tipo de los valores que va a guardar (todos los valores que guarda tienen que ser del mismo tipo), a continuación el nombre de la variable y entre corchetes el tamaño. El tamaño debe ser fijo y estar definido en una constante de tipo entero. Para saber que tamaño debes darle al array mira la descripción de la entrada en el enunciado del problema.
Para acceder a cada componente del array se utiliza su posición. La primera posición es la cero. Por lo tanto la última será el número de valores que guarda menos uno. Por ejemplo, el siguiente código declara un array, lee los valores del teclado y calcula su suma.
const int MAX = 1000;
void resuelveCaso()
...int numElem; std::cin >> numElem;
...int array[MAX];
...... for (int i = 0; i < numElem; ++i)
...... std::cin >> array[i];
... int suma = 0;
... for (int i = 0; i < numElem; ++i)
...... suma += array[i];
... std::cout << suma;
Para ordenar los datos de un array debéis utilizar la función sort de la librería algorithm. Cómo estamos utilizando arrays y no vectores, la instrucción adecuada es: std::sort(v,v+TAM); siendo v el array y TAM el número de elementos del array. La instrucción ordena los valores en orden creciente desde el cero hasta TAM.
Para otros tipos de ordenación consultar las transparencias de clase.
En algunos de estos problemas es necesario guardar todos los datos de entrada para después ordenarlos. Para guardar colecciones de valores del mismo tipo se utilizan una variable de tipo array. Para declarar la variable debéis indicar el tipo de los valores que va a guardar (todos los valores que guarda tienen que ser del mismo tipo), a continuación el nombre de la variable y entre corchetes el tamaño. El tamaño debe ser fijo y estar definido en una constante de tipo entero. Para saber que tamaño debes darle al array mira la descripción de la entrada en el enunciado del problema.
Para acceder a cada componente del array se utiliza su posición. La primera posición es la cero. Por lo tanto la última será el número de valores que guarda menos uno. Por ejemplo, el siguiente código declara un array, lee los valores del teclado y calcula su suma.
const int MAX = 1000;
void resuelveCaso()
...int numElem; std::cin >> numElem;
...int array[MAX];
...... for (int i = 0; i < numElem; ++i)
...... std::cin >> array[i];
... int suma = 0;
... for (int i = 0; i < numElem; ++i)
...... suma += array[i];
... std::cout << suma;
Para ordenar los datos de un array debéis utilizar la función sort de la librería algorithm. Cómo estamos utilizando arrays y no vectores, la instrucción adecuada es: std::sort(v,v+TAM); siendo v el array y TAM el número de elementos del array. La instrucción ordena los valores en orden creciente desde el cero hasta TAM.
Para otros tipos de ordenación consultar las transparencias de clase.
Estos problemas están fuera del temario del curso y se proponen únicamente para los alumnos que quieran participar en los concursos de programación o avanzar más en el tema algoritmico. Estos problemas se resuelven con temas de asignaturas de cursos posteriores.
Para resolver estos problemas es necesario utilizar búsqueda binaria, bien sobre un vector, bien sobre un intervalo de valores. La búsqueda binaria se aplica solo sobre colecciones de datos ordenadas y busca un elemento en una colección se forma mucho más eficiente que la búsqueda secuencial. Por este motivo, soluciones que dan TLE utilizando la búsqueda secuencial entran en tiempo si se utiliza búsqueda binaria. La búsqueda binaria se puede implementar de forma iterativa mediante un bucle o de forma recursiva llamando a la propia función con unos valores "mas pequeños". Este algoritmo se encuentra implementado en las funciones lower_bound y upper_bound de la librería algorithm.
Vamos a empezar proponiendo dos problemas.
En el primero (hoy comemos mejillones) se debe buscar la estrategia óptima para colocar los mejillones en el plato. Se puede resolver utilizando la función lower_bound de la librería para realizar la búsqueda binaria.
En el segundo (viajando con el abuelo) se debe realizar una búsqueda binaria sobre el espacio de soluciones. Para ello pensad el intervalo de valores entre los que se encuentra la solución y calcular las paradas que se realizan si se supone el tiempo medio del intervalo. En función del numero de paradas obtenidas para el tiempo medio decidid si debéis buscar la solución en la parte izquierda del intervalo de soluciones o en la parte derecha.
Estos problemas están fuera del temario del curso y se proponen únicamente para los alumnos que quieran participar en los concursos de programación o avanzar más en el tema algoritmico. Estos problemas se resuelven con temas de asignaturas de cursos posteriores.
Para resolver estos problemas es necesario utilizar tipos de datos de la librería STL, como unordered_set, set, unordered_map, map, priority_queue...
Estos problemas están fuera del temario del curso y se proponen únicamente para los alumnos que quieran participar en los concursos de programación o avanzar más en el tema algoritmico. Estos problemas se resuelven con temas de asignaturas de cursos posteriores.
Los problemas son variados, unos se resuelven con un algoritmo iterativo, otros con algoritmos recursivos. En algunos hacen falta TADs com las colas de prioridad o los conjuntos o maps. En algunos hace falta el tipo stringstream (que se puede encontrar en las transparencias de clase en el tema 2.8 al final) para leer los datos o convertir cadenas de caracteres a números.