100 - The 3n + 1 problem

[jack1082]

This is my code to problem 100, but I got a WA, can someone tell me where I did wrong?

#include<stdio.h>
#include<stdlib.h>
int main(void) {
int i,j,num,tmp,cycle,n=1;
scanf("%d %d",&i,&j);
if ((0<i<1000000) && (0<j<1000000)) {
int p=i>j?j:i;
int q=i<j?j:i;


for (num=p;num<=q;num++) {
tmp=num;
cycle=1;
while(tmp!=1) {
if (!(tmp%2)){tmp=tmp/2;}
else {tmp=tmp*3+1;}
cycle+=1;
}
n=n>=cycle?n:cycle;
}

printf("%d %d %d\n",i,j,n);
}
}

[helloneo]

http://online-judge.uva.es/board/viewtopic.php?t=3015

[jack1082]

This is my code to problem 100, but I got a WA, can someone tell me where I did wrong? Thanks!

#include<stdio.h>
#include<stdlib.h>
int main(void) {
int i,j,num,tmp,cycle,n=1;
scanf("%d %d",&i,&j);
if ((0<i<1000000) && (0<j<1000000)) {
int p=i>j?j:i;
int q=i<j?j:i;


for (num=p;num<=q;num++) {
tmp=num;
cycle=1;
while(tmp!=1) {
if (!(tmp%2)){tmp=tmp/2;}
else {tmp=tmp*3+1;}
cycle+=1;
}
n=n>=cycle?n:cycle;
}

printf("%d %d %d\n",i,j,n);
}
}

[newton]

get more information from
http://online-judge.uva.es/board/viewto ... sc&start=0

[arakdev]

I have solved it and got correct answers , but how much ases it should process and read, the termination condition wasn't mentioned in the problem. If we want to get all inputs at a time , how we undrestand the end of input ?

[helloneo]

http://online-judge.uva.es/board/viewto ... &start=150

Don't open a new thread, if it exits already..

[rich_correia]

Hi

I just started solving a couple problems today. As I was wondering about the site I noticed that, while my runtime to problem 100, (the 3n+1 thing), was something relatively lengthy other people had runtimes of 0 and 0.001, something like that, very fast.
Do they write parts of the code in assembler? What gives?

Rich

[rio]

pre-calculate teq, and fast i/o.

[rich_correia]

sorry dude, what does precalculated teq mean?

[Debashis Maitra]

precalculated teq means precalculated output

[newton]

it takes about 4.017 sec to exicute the programe in OJ.
it is so much, how can i minimize my time limit?
any new algorithm?
plz help me.

Code: Select all

#include <stdio.h>

int main(void)
{
   long i,j,m,temp,total,max;
   while(scanf("%ld %ld",&i,&j)==2)
   {
	  printf("%ld %ld ",i,j);
	  max=0;
	  if(i>j)
	  {
		temp=i;
		i=j;
		j=temp;
	  }
	  for(m=i;m<=j;m++)
	  {
		temp=m;
		total=0;
		while(1)
		{
			if(temp==1 && temp)
			{
				total++;
				break;
			}
			total++;
			if(temp % 2 == 0)
				temp/=2;
			else
				temp=( 3 * temp + 1 );
		}
		if(total>max)
			max=total;
	  }
	  printf("%ld\n",max);
   }
   return 0;
}

[shamim]

You could use precalculation and memoization.
That is, precalculate all the values first. Now, when finding the cycle length for 32 you need to find that of 16. So, there is no need to calculate the cycle length of 16 twice.

[Roby]

AND print the formatted output directly

But I a little bit curious about the fast I/O... I always use gets to make my solution faster... but it was "less" faster than I thought... So, can someone give me an example how to make fast I/O parser? Thanks.

[Vexorian]

In a less esoteric way of doing things, 100 has a fast solution in which you keep an array as a table for solutions you got already. For example f(15) requires your to solve f(46) so if you later go through f(46) you don't have to calculate f(46) again since the program 'remembers' the solution for it.

A good thing to do is to solve http://acm.uva.es/problemset/v3/371.html after solving 100 and notice the differences.

[statefull]

Hi all!

Judge don't want accept my program

always WA.... The examples in page works fine

Somebody that resolved the problem could put some example with the solutions

thanks


EDIT:
OK i obtein accepted jeje I put examples:

INPUT
1 1
1 2
1 3
1 4
100 500
1 10000
3432 2991
2391 2931
787843 100
OUTPUT
1 1 1
1 2 2
1 3 8
1 4 8
100 500 144
1 10000 262
3432 2991 199
2391 2931 217
787843 100 509

regards