UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Entrega: 28 de marzo de 2006 a las 10pm

Cada una de las siguientes cinco preguntas vale 5 puntos. Pueden usar la técnica que más les convenga pero sus códigos deben sujetarse a las especificaciones de entrada y salida, además de que deben de producir soluciones correctas (aunque no necesariamente óptimas). Cada problema se evaluará con 5 casos de prueba. Quien obtenga la mejor solución de cada caso de prueba obtendrá 1.0 puntos en ese caso y los demás obtendrán una calificación proporcional entre 0.0 y 1.0.

Problema 1: Cajas de madera (madera.c, madera.cpp, madera.java)

Suponga que N artículos diferentes se deben empacar en cajas de madera. Suponga que el costo de construir una caja para el artículo I (donde 1 <= I <= N) es de CI pesos donde C1 > C2 > ... > CN, lo cual también refleja el hecho de que los artículos están ordenados de modo que el artículo 1 es el más grande, el artículo 2 es el segundo más grande, y así sucesivamente, siendo el artículo N el más pequeño. Como ejemplo, suponga que N = 10 y que (C1, C2, ..., C10) = (32, 30, 20, 17, 15, 10, 9, 5, 3, 2). Si pudieramos construir una caja de cada tamaño, entonces el costo de empacar todos los artículos sería simplemente C1 + C2 + ... + C10. Sin embargo, suponga que sólamente podemos construir cajas de a lo sumo M tamaños distintos, pero que una caja en donde se pueda empacar el artículo I se puede usar para empacar cualquier artículo J más pequeño que el artículo I. Por ejemplo, si M = 5 podríamos construir dos cajas para el artículo 1, dos cajas para el artículo 3, tres cajas para el artículo 5, una caja para el artículo 8 y dos cajas para el artículo 9. El costo de esto sería de 2C1 + 2C3 + 3C5 + C8 + 2C9 = 160. El problema es el de determinar cuáles son los M tamaños de cajas que se deben construir y cuántas cajas de cada uno de esos M tamaños se deben construir para minimizar el costo T de empacar todos los artículos.

Entrada: Se leerá desde la entrada estándar y consistirá de dos líneas. La primera línea contendrá los valores enteros de N y M separados por un espacio. La segunda línea contendrá los N valores enteros C1, C2, ..., CN separados por espacios. Puedes suponer que 1 <= N <= 100, 1 <= M <= 10, M <= N y que 1000 > C1 > C2 > ... > CN > 0.

Salida: Se escribirá en la salida estándar y consistirá de dos líneas. La primera línea contrendrá el costo mínimo T. La segunda línea contendrá N valores enteros A1, A2, ..., AN separados por espacios, donde AI es el número de cajas para el artículo I. Observa que de acuerdo al enunciado del problema, no más de M de estos valores podrán ser positivos y además A1 + A2 + ... + AN = N.

Ejemplo de entrada y salida:
Entrada
 Salida
10 5
32 30 20 17 15 10 9 5 3 2
 153
2 0 1 2 0 2 0 3 0 0

Problema 2: Dos funciones recursivas (pifipi.c, pifipi.cpp, pifipi.java)

Considere dos funciones llamadas fi(x,a) y pi(x), ambas con parámetros enteros, que se calculan recursivamente de la siguiente manera: Si a > 1 entonces fi(x,a) = fi(x,a-1) - fi(x/p, a-1), donde p es el a-ésimo número primo (es decir, el elemento número a de 2, 3, 5, 7, 11, ...) y x/p es la parte entera de la división. Si a = 1, entonces fi(x,1) es la parte entera de (x+1)/2. Además, fi(x,a) = pi(x) - a + 1, donde a = pi(sqrt(x)), donde sqrt(x) es la parte entera de la raíz cuadrada de x, y pi(1) = 0, pi(2) = 1 y pi(3) = 2. El problema es el de determinar pi(x) para diferentes valores de x.

Entrada: Se leerá desde la entrada estándar y consistirá de una línea, la cual contendrá el valor del entero x, donde 1 <= x <= 100000.

Salida: Se escribirá en la salida estándar y consistirá de una línea, la cual contendrá el valor de pi(x).

Ejemplo de entrada y salida:
Entrada
 Salida
1000
 168

Problema 3: Vaciar vasos de precipitados (vaciar.c, vaciar.cpp, vaciar.java)

Tenemos tres vasos de precipitados, todos ellos con el mismo volumen V y con una cierta cantidad N de marcas indicando el volumen que se puede medir desde el fondo del vaso hasta la marca. Al principio, el vaso 1 está lleno de un líquido muy valioso y los vasos 2 y 3 están vacíos. Se desea saber el mínimo número M de pasos necesarios para separar W unidades de este líquido en cualquiera de los tres vasos. La operación permitida a cada paso es la de vertir el líquido de un vaso a otro hasta que el nivel del líquido en cualquiera de estos dos vasos coincida con una marca o hasta que cualquiera de estos dos vasos quede vacío o lleno. Como el líquido es muy valioso, no se permite perderlo en el proceso.

Entrada: La primera línea de la entrada contiene tres enteros V, W y N. La segunda línea contiene N enteros X1, X2, ... XN: las posiciones de las marcas. Puedes suponer que 0 < W < V <= 1000 y que 0 < X1 < X2 < ... < XN < V.

Salida: La primera línea de la salida contiene el entero M (1 punto). Cada una de las siguientes M líneas deberá contener tres enteros A, B y C, donde A es el vaso de donde se vierte el líquido al vaso B y C es la cantidad de líquido que se transfiere a cada paso (2 puntos).

Ejemplo de entrada y salida:
Entrada
 Salida
10 5 3
1 6 7
 2
1 2 6
2 3 1

Problema 4: Cortar rectángulos en cuadrados (cortar.c, cortar.cpp, cortar.java)

Se tiene un rectángulo cuyos lados tienen longitudes enteras. Tú quieres cortar ese rectángulo en el número mínimo posible de cuadrados cuyos lados también tengan longitudes enteras. Los cortes se pueden hacer con una máquina que sólo puede cortar en las direcciones paralelas a los lados del rectángulo y cortando a lo largo de todo el rectángulo. Los rectángulos que se vayan obteniendo se deben cortar por separado de la misma forma.

Entrada: La primera línea de la entrada contiene dos enteros positivos A y B, las longitudes de los lados del rectángulo. Cada lado del rectángulo es al menos 1 y a lo más 1000.

Salida: La primera línea de la salida contiene un entero N, el número mínimo de cuadrados. Las siguientes A líneas contienen B enteros del 1 al N describiendo los cuadrados.

Ejemplo de entrada y salida:
Entrada
 Salida
5 6
 5
1 1 1 4 4 4
1 1 1 4 4 4
1 1 1 4 4 4
2 2 3 3 5 5
2 2 3 3 5 5

Problema 5: Permutaciones divisibles (divide.c, divide.cpp, divide.java)

Escribe un programa que encuentre todas las permutaciones (A1, A2, ..., An) del conjunto {1, 2, ..., n} tales que A1+A2 sea divisible entre 2, A2+A3 sea divisible entre 3, y así sucesivamente, hasta que An-1+An sea divisible entre n. Por ejemplo, para n = 3, la única permutación de {1, 2, 3} que cumple estas condiciones es (3,1,2), puesto que 3+1 es divisible entre 2 y 1+2 es divisible entre 3.

Entrada: La primera línea de la entrada contiene un entero positivo N entre 2 y 20.

Salida: La salida deberá consistir de las permutaciones que cumplan esta condición, una en cada renglón, con sus elementos separados por un espacio.

Ejemplo de entrada y salida:

Entrada
 Salida
3
 3 1 2