viernes, 12 de marzo de 2010

100-3n+1

The famous problem 3n+1 is a problem NP. Try to improve my time


/*

Judge : Uva
Number: 100
Name : 3n+1
Time: 0.028
*/

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000001
#define SWAP(a, b) { a ^= b;b ^= a;a ^= b;} /*swapping*/

unsigned long conta[MAX];

unsigned long tres(unsigned long n)
{
if(n<MAX)
{
if(conta[n]==0) conta[n]=(n&1)?1+tres(3*n+1):1+tres(n>>1);
return conta[n];
}
else
{
if(n%2) return 2+ tres((3*n+1)>>1); /*how n is > MAX */
else return 1+ tres(n>>1);
}

}
int main()
{

unsigned long a,b,c,d,maximo,i,temp;
for(i=0;i<=MAX;i++) //init table
conta[i]=0;
conta[1]=1;
while(scanf("%lu%lu",&a,&b)==2)
{
c=a;
d=b;
if(a>b) SWAP(a,b);
maximo=0;
for(i=a;i<=b;i++)
{
if(conta[i]==0)
conta[i]=tres(i);
if(maximo<conta[i])
maximo=conta[i];
}
printf("%lu %lu %lu\n",c,d,maximo);
}
return 0;
}

1 comentario:

Anónimo dijo...

te recomiendo utilizar la libreria standar busca en internet y aprendela y tambien el algorithm y string te ayudaran mucho , y recuerda que tienes que aprender a optimizar el codigo ya que casi siempre uno resuelve bien el problema pero tarda mucho y te bota el pc2 time exceded