Reto
Programacion
Tomando en cuenta los retos que ha puesto asarch. (El primero usando unos comando de shell para hacer renombrado de grupos de archivos y el segundo de modificar el programa en C de saidjosé para que tomara los parámetros desde la línea de comandos, en estilo BSD y GNU). Ahora quisiera poner uno pequeño pero que tiene que ver con lógica y programación. Trataré de poner todas las restricciones que tenga el problema para encontrar la manera óptima de resolverlo.
Veamos el siguiente planteamiento:
Un pintor quiere pintar una línea de casas de un fraccionamiento, solamente es una calle. Y lo tiene que hacer de diferentes colores sin que un color se repita para 2 casas adyacentes, solamente cuenta con 3 colores para elegir. El tiempo para pintar una casa dependerá del tamaño de la casa, del color a utilizar y del color que tenga la casa en ese momento. El problema para el pintor es que necesita hacerlo lo más rápido posible, porque entre menos días se tarde ganará más, y podría seguir pintando algún fraccionamiento.
Entrada: Constará de un entero n en la primera línea, que dice el número de casas. Seguido de n líneas, cada una con 3 enteros representando el tiempo que se tardará el pintor en esa casa para cada color. Podrá haber hasta 10,000 casas.
Salida: Simplemente se debe imprimir el tiempo mínimo para pintar todas las casas.
Ejemplo:
Entrada:
3
26 40 83
49 60 57
13 89 99
Salida:
96
Restricciones: Se puede hacer en cualquier lenguaje de programación, hasta se puede solucionar simplemente con pseudocódigo. La restricción es que debería correr en menos de 1 segundo, para eso tomaremos como base que aproximadamente 1000,000,000 de operaciones (sumas, restas, comparaciones, etc) se ejecutan en aproximadamente 1 seg.
Cualquier duda que tengan sobre el problema, se las puedo aclarar. Si necesitaran ayuda sobre como leer la entrada o desplegar la salida, también se puede apoyar con eso.
Permalink: http://www.mononeurona.org/users/entry/thot/1531
Comentblogs:
thot wrote: Más bien como ejercicios de las olimpiadas de informática o algo asÃ.
2008-09-02 16:03:15-05
thot wrote: Espero te parezca interesante vendaval. Tomando en cuenta que la otra vez mencionaste que te agradaban esas cuestiones.
2008-09-02 16:49:15-05
asarch wrote: Dandole una segunda leida tu planteamiento encuentro que tiene un bug:
"El problema para el pintor es que necesita hacerlo lo más rápido posible, porque le pagarán por dÃas."
Si lo hace rapido == menos dias == menos dinero
Si lo hace despacio == mas dias == mas dinero
Digo...
2008-09-02 22:01:25-05
thot wrote: Sà tienes razón, serÃa la cuestión de que entre menos tiempo más dinero. Para que tuviera chiste todo esto. :P.
2008-09-02 22:13:27-05
thot wrote: Ya corregà el detalle de redacción asarch, ahora sà te puede poner a resolver el problema sin ninguna duda. (Y cualquiera que surja, pues trataré de responderla). Mil disculpas por los problemas de redacción, eso de escribir las cosas al trancazo no es muy bueno.
2008-09-03 11:02:47-05
Pike wrote: //a ver si te gusta mi solución en c++
#include <iostream>
using namespace std;
int n;
int casas[10000][3];
int optimo[10000][3];
inline int calcula_minimo(int a, int b){
if (a<b) return a;
return b;
}
int calcula_optimo(int pos, int color){
int minimo;
if (pos>=n || color>=3) return 0;
if(optimo[pos][color] != -1)
return optimo[pos][color];
if (color==0)
minimo=casas[pos][color]+calcula_minimo(calcula_optimo(pos+1, 1),calcula_optimo(pos+1, 2));
else
if (color==1)
minimo=casas[pos][color]+calcula_minimo(calcula_optimo(pos+1, 0),calcula_optimo(pos+1, 2));
else
minimo=casas[pos][color]+calcula_minimo(calcula_optimo(pos+1, 0),calcula_optimo(pos+1, 1));
optimo[pos][color]=minimo;
return minimo;
}
int main(){
cin >> n;
for (int i=0; i<n; i++)
for (int j=0; j<3; j++){
cin >> casas[i][j];
optimo[i][j]=-1;
}
cout << calcula_minimo(calcula_optimo(0, 0), calcula_minimo(calcula_optimo(0, 1), calcula_optimo(0, 2)));
return 0;
}
2008-10-27 11:52:32-06
thot wrote: Pues se ve más o menos, solo que la pregunta del millón es... ¿Corre en tiempo? ;)
2008-10-27 13:18:15-06
Pike wrote: Pues no se wey, fue la primera solucion que se me ocurrió, pasame la entrada con las 10,000 casas y lo pruebo.
2008-10-28 09:55:31-06
thot wrote: jajajaja, che pike, con la pura complejidad del algoritmo podrÃas probarlo. No tienes ninguna poda, si te fijas es más o menos como el problema que pusieron en la del Golfo. Entonces yo digo que tu solución no corre en tiempo, ni queriendo.
2008-10-28 10:12:04-06
Pike wrote: ah caray! JurarÃa que esto es una poda =S
if (pos>=n || color>=3) return 0;
if(optimo[pos][color] != -1)
return optimo[pos][color];
Ni pedo, no tendras un manual de programación en pdf que me puedas enviar?
2008-10-29 12:48:47-06
Pike wrote: bueno le platiqué al Pibe sobre el problema y esta es su solución
// Que te parece mi solucion en C
#include <stdio.h>
int casas[100001][3];
int min(int a, int b){
return (a < b ? a: b);
}
int main(){
int n,i,j,a,b,c, r;
scanf("%d",&n);
for(i=0; i<n; i++){
scanf("%d %d %d",&a,&b,&c);
if(i > 0){
casas[i][0] = a + min(casas[i-1][1],casas[i-1][2]);
casas[i][1] = b + min(casas[i-1][0],casas[i-1][2]);
casas[i][2] = c + min(casas[i-1][0],casas[i-1][1]);
}else{
casas[i][0] = a;
casas[i][1] = b;
casas[i][2] = c;
}
}
r = min(casas[n-1][0],casas[n-1][1]);
r = min(r,casas[n-1][2]);
printf("%d\n",r);
}
2008-10-29 13:54:41-06
Pike wrote: Bueno, sigo platicando con ese wey, el pichon no sabe como agregar comentarios, aquà les dejo otro código de la posible solución, para que corra en tiempo y no consuma memoria innecesaria...
#include <stdio.h>
int min(int a, int b){
return (a < b ? a: b);
}
int main(){
int i, temp1, temp2, temp3, color1, color2, color3, n;
scanf("%d",&n);
scanf("%d %d %d",&color1,&color2,&color3);
for (i=1; i<n; i++){
scanf("%d %d %d",&temp1,&temp2,&temp3);
color1 = temp1 + min(color2,color3);
color2 = temp2 + min(color1,color3);
color3 = temp3 + min(color1,color2);
}
printf("%d\n",min(color1, min(color2, color3)));
}
P.D. oye Tooth y es posible que el numero de casas sea 0? para validar, y cual debe ser la respuesta? 0?
2008-10-29 14:05:32-06
thot wrote: No, está bien asÃ, el número de casas no puede ser 0. Y ya esas últimas respuestas ya tienen más sentido tomando las restricciones de tiempo ;). Tu solución recursiva podrÃa funcionar tomando en cuenta que es usaste la memoization. Pero realmente una solución bottom-up como las 2 últimas es la más conveniente. Saludos.
2008-10-30 10:35:46-06
Pike wrote: oye wey, dice el pibe que ya pongas otro u.u pero que no este tan pichon, unos más dÃficil...
2008-10-31 11:32:51-06
thot wrote: jajaja, este fue orientado a gente que no programa tanto. Espero ya volver a retomar todo ese desmadre en un tiempo, entonces ya pondré problemas más interesantes...
2008-10-31 17:47:42-06
Oscar wrote: Mmm, no sé, puede ser que esté viendo mal, pero se me hace que por la forma en que reasigna sus valores Pike en la última solución, no va a acarrear la respuesta correcta U_U.
Y qué onda, cuándo posteas tu respuesta y nuevos problemas de estos, saludos.
2008-11-07 16:47:14-06
thot wrote: Pues ya mero, nada más que tenga un poco de tiempo. En este caso me parece que sà sacarÃa la respuesta correcta, el último programa que enviaron.
2008-11-07 17:18:55-06
