| Enviar | Todos los envíos | Mejores soluciones | Atrás a la lista |
CC13B - Problema B |
En las clases de Estructuras de Datos, como es de saberse, los proyectos que se dejan normalmente se desarrollan de manera grupal para que de alguna forma se logre motivar a los estudiantes a trabajar y compartir ideas, lo cual ayuda en el proceso de aprendizaje y refuerza aspectos de la vida profesional. Hace muy poco, el docente encargado del curso, mientras enseñaba la estructura de datos llamado Heap de Fibonacci (usado en una variante del algoritmo Dijsktra donde la tarea es buscar la ruta mínima entre 2 vértices de un grafo conexo y acíclico) decidió dejar a sus alumnos como tarea la implementación de dicha estructura. Como el trabajo es grupal, el profesor quiere restringir el modo de como se forman normalmente los grupos (que es por un máximo número de integrantes por grupo) a lo siguiente: La suma de las edades de los integrantes de un grupo no debe de ser mayor a un valor K. El problema es que el profesor quiere saber cuantos grupos como mínimo se pueden formar para un valor dado de K y de acuerdo a ello distribuir su tiempo para revisar los trabajos. Si K es muy grande, quizá la mitad del salón pueda formar parte de solo un grupo!, pero si K es muy pequeño, es posible que cada grupo esté conformado por solo un estudiante. Aunque el cálculo del valor K se puede hacer a mano, resulta algo tedioso en caso de que el docente piense en futuros trabajos que sigan la misma metodología.
Lamentablemente el docente se encuentra muy ocupado preparando una charla sobre Red-Black Tree, y no tiene mucho tiempo para diseñar un algoritmo que le ayude en la búsqueda del valor K, así que tienes que ayudar al docente. Se te dará la descripción de las edades de los alumnos de la clase de Estructuras de Datos junto con un valor K, y tu tarea es formar el mínimo número de grupos posibles que cumplan con la condición antes expuesta. Con esto ayudaras al docente a elegir el valor de K según el mejor criterio que él vea por conveniente. Yá para otra oportunidad tu tarea será elegir el valor K óptimo.
Entrada
El archivo de entrada contiene varios casos de prueba. La primera líea de cada caso de prueba contiene dos enteros N y K, donde N es el número de alumnos que llevan el curso de Estructuras de Datos, y K es el valor máximo que puede resultar la suma de las edades de cada grupo (1 ≤ N ≤ 20, (max 1≤i≤N Ei) ≤ K ≤∑i=1NE i). Los siguientes Ei enteros (1 ≤ i ≤ N, 15 ≤ Ei ≤ 35) describirán las edades de los N estudiantes.
La entrada termina cuando N = 0.
Salida
Para cada paso de prueba de la entrada imprimir una lnea:
“Caso #T: M”(sin comillas)
donde T representa el número de caso de prueba, y M el míimo número de grupos que se puede formar con el valor de K. Ver el ejemplo de salida para más detalles.
|
|
|
| Ejemplo de Entrada | Ejemplo de salida para la entrada |
|
|
|
| 5 35 | Caso #1: 3 |
| 15 20 21 18 15 | Caso #2: 4 |
| 10 70 | Caso #3: 2 |
| 19 21 22 20 | |
| 22 20 | |
| 21 23 24 22 | |
| 4 47 | |
| 16 18 17 20 | |
| 0 111 | |
|
|
|
| Adicionado por: | Walter Erquinigo |
| Fecha: | 2013-10-25 |
| Tiempo límite: | 1s |
| Límite del código fuente: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Lenguajes: | Todo excepto: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Fuente: | 5to-CusContest |
RSS