Autor Tema: Problemas con 100 ACM UVA (Leído 5713 veces)

« **en:** Marzo 09, 2006, 12:48:40 pm »

?La entrada de los datos debe ser como argumento o les pide dentro del programa?

yo el programa lo tengo hecho, pero no he usado ningun tipo de optimizacion...lo he hecho a lo bruto sin mas. Creo que tengo que mejorarle por que con valores grandes(a partir de 100000 tarda muchoo) tarda la de dios y supongo que pueden tirar nuestro programa por eso.

Fdo: Anacoreta

PD: ?Se pueden postear programas aqui o esta prohibido para no joder a los demas?

HQH · « **Respuesta #1 en:** Marzo 09, 2006, 01:37:53 pm »

Puedes postear cosas siempre que no sean la solucion exacta. (De todas maneras quien lo mire, es su problema).

Mejor postea estas cosas en foro de algoritmica, la idea de este subforo es que fuera solo para soluciones.

Por cierto, la entrada es la entrada y salida estandard, no son argumentos ni nada asi.

Un saludo.

« **Respuesta #2 en:** Marzo 09, 2006, 01:53:05 pm »

Y cual son las causas por las cuales te devuelve el erro "Wrong answe", por que mi programa devuelve bien los datos y correctos, el unico problema que puede dar es el de excesivo tiempo, pero he visto que ese es otro error distinto.

Código: [Seleccionar]

#include <stdio.h>
int main ()
{
	int i,j,tmp,cont,n,max;
	scanf ("%d %d", &i, &j);
	printf ("%d %d ",i,j);
	if (i>j)
	{
  tmp=i;
  i=j;
  j=tmp;
	}
	max=0;
	for (n=i;n<=j;n++)
	{
  tmp=n;
  cont=1;
  while (tmp!=1)
  {
  	cont++;
  	if (tmp%2==0) 
    tmp=tmp/2;
  	else
    tmp=(3*tmp)+1;
  }
  if (max<cont)
  	max=cont;
	}
	printf (" %d\n", max);
	return 0;
}

Si es solo para soluciones este foro aqui teneis la mia...aunque no es valida

?Alguien ve el posible fallo? Si en este que es sencillo ya tengo problemas...mal vamos.

Anacoreta.

HQH · « **Respuesta #3 en:** Marzo 09, 2006, 02:12:06 pm »

Hola amigo, primero voy a decirte que muevo este trozo de post (menos mi solucion) al subforo de algoritmica.

No te desanimes, todos hemos tenido problemas al empezar, con ganas aprenderas un monton.

Segundo te respondo a tus dudas. Es bastante pu?etero el sistema de entrada y salida por caracteres que a veces te meten al final y tal. Yo para eso recomiendo usar c++ (cin y cout, aunque solo uses esa parte en C++ y todo lo demas en C), que son super faciles de usar.

Te doy alguna pista : Una cosa esta mal. Tu programa solo funciona para un caso. El programa que piden debe funcionar para tantos casos como pida el fichero, hasta que este finalice. Estas cosas suelen ir definidas en el problema. "The input will consist of a series of pairs of integers i and j, "

Segundo si en un futuro tubieras problemas de tiempo te comento una cosa : Hay una forma de DIVIDIR POR 2 mas optima computacionalmente que la que usas

Un saludo.

Phas · « **Respuesta #4 en:** Marzo 09, 2006, 06:43:56 pm »

Citar

Segundo si en un futuro tubieras problemas de tiempo te comento una cosa : Hay una forma de DIVIDIR POR 2 mas optima computacionalmente que la que usas

Ya puestos, si lo que queremos es ahorrarnos divisiones, tambi?n pod?amos decir que hay una forma de saber si un numero es divisible por dos mucho mas r?pido que calcular "numero%2"... du yu ANDerstan 1o que digo?

« **Respuesta #5 en:** Marzo 10, 2006, 12:33:15 am »

Para dividir por 2, supongo que sera m?s r?pido a>>1 no?

pero lo del modulo..como se comprueba que el ultimo bit es un 0?....ma?ana lo miro, hoy voy a dormir un rato.

Anacoreta

HQH · « **Respuesta #6 en:** Marzo 10, 2006, 12:49:30 am »

Esto es una cosa mas del lenguaje ya que conoces la idea.
Seria en C con un and de bits (&, no confundir con && que es el and logico) ejemplo variable&1 en variables sin signo

« **Respuesta #7 en:** Marzo 15, 2006, 11:46:06 am »

Veamos tengo una duda sobre la entrada/salida de datos. Como se debe hacer:

a) Se introduce una linea y devuelve resultado, otra linea y devuelve, etc...

b) Se intrroducen todas las lineass y al final devuelve todos los resultados.

Sabiendo esto, cre que tendria acabado el programa y listo para enviar.

Un saludo!!

Anacoreta

HQH · « **Respuesta #8 en:** Marzo 15, 2006, 12:28:33 pm »

Se recibe un juego de prueba, se procesa y se devuelve la respuesta, hasta que acaben los juegos de prueba.

Nota : no uses el concepto linea, ya que en otros programas un juego de prueba no tiene porque ser una linea solo(va definifo en el enunciado). Un saludo.

« **Respuesta #9 en:** Marzo 16, 2006, 11:45:13 am »

Despues d seguir los sabios consejos de Phas y HQH y optimizar todo lo que soy capaz el c?digo sigue sin ser valido. Me tira por un time limit, y lo ve l?gico por que con numeros mayors de 100.000 tardaa la de dios...

Código: [Seleccionar]

#include <stdio.h>
int main ()
{
        int i,j,max,cont,tmp,n;
        while (scanf("%d %d",&i,&j))
        {
                printf ("%d %d ",i,j);
                if (j<i)
                {
                        i=i^j;
                        j=j^i;
                        i=j^i;
                }
                max=0;
                for (n=i;n<=j;n++)
                {
                        tmp=n;
                        cont=1;
                        while (tmp!=1)
                        {
                                if (tmp&1)
                                        tmp=3*tmp+1;
                                else
                                        tmp=tmp>>1;
                                cont++;
                        }
                        if (max<cont)
                                max=cont;
                }
                printf ("%d\n",max);
        }
}

?Alguna sugerencia para mejorar?

Lo de hacer el intercambio entre i y j mediantee XORS no es necesario por que solo se hace una vez, pero ya que estabamos puestos a mejorar...

Un saludo y gracias de antemano!

Anacoreta

HQH · « **Respuesta #10 en:** Marzo 16, 2006, 01:21:52 pm »

Yo creo, que salvo que me haya dejado algun detalle sin ver, esta bien. Yo para leer los juegos de pruebas suelo usar cin de c++ (y printf para imprimir) es mas practico y da menos problemas, con scanf alguna vez tube algunos.

Aun asi, te digo una cosaa tener en cuenta, yo no usea la optimicacion tmp&1 y si quieres usarla debes tener una cosa clara: ??Como se representa tmp??? Tal como lo tienes es con signo. ??Sin signo seria igual??

Un saludo.

« **Respuesta #11 en:** Marzo 16, 2006, 01:35:01 pm »

He estado haciendo unas pruebas de optimizaci?n con el time de linux y he visto varias cosas:

1) el uso de xor para intercambiar los valores de las variables es menos efectivo que el intercambio con una tercera variable temporal, asi que eso lo elimino.

2) Otra cosa que he visto es que tarda lo mismo en hacer (x % 2) que en hacer (x & 1), asi que lo dejare con el modulo que se que no da problemas.

3) Por ?ltimo lo que si que gana tiempo es la divisi?n a nivel de bits x>>1 con respecto a x/2.

Las pruebas las he realizado con un bucle que hac?a 1.000.000 de operaciones. Quitando estos detalles no he visto por donde mejorarlo...voy a enviarlo a ver s hay suerte.

Un saludo y gracias!

PD: Ya encontre el fallo, se da la vuelta la variable tmp...he probadon con unsgined long int pero estoy en las mismas....ya inventare algo...

HQH · « **Respuesta #12 en:** Marzo 17, 2006, 04:13:47 pm »

Comentarte una cosa. Con las medidas que propones, hay mas que suficiente para pasar el reto (Yo lo hice con todo eso). Parece que el problema quizas esta en como lees el fichero, te recomiendo usar cin o sino leer un %c para leer el \n y que no se te quede parado o alguna solucion asi.

Si sigues teniendo problemas, y como caso excepcional, puedes ponerte en contacto y te envio el mio.

« **Respuesta #13 en:** Marzo 17, 2006, 04:44:38 pm »

No, ya encontre el problema, lo puse en el PD del anterior post...la variable donde voy guardando los valores del ciclo (tmp) llega un punto en que se da la vuelta y toma valores negativos...y entonces nunca sale de ese bucle.

He probado con unsigned long int pero aun asi la variable se queda corta...vere que se me ocurre...pero esta feo el asunto. Esto en ruby o php no pasaria

Un saludo!!

Anacoreta

HQH · « **Respuesta #14 en:** Marzo 17, 2006, 08:46:21 pm »

El problema no va por ahi. Lee el enunciado, pone que en ningun caso hara overflow a una variable de 32 bits.

"You can assume that no opperation overflows a 32-bit integer."

int i,j,k;

La k es donde imprimo yo el resultado, tienes algo mal en la convergencia ya que con un int sobra, he usado int en todo el programa.