100 - The 3n + 1 problem

[mf]

You get WA because your code throws an exception (I guess there could be leading spaces or more than one space between numbers), which you catch and silently exit. You don't have to do that. If your main() throws exceptions, it's OK, you'll just get a "Runtime Error" verdict instead of WA.

Scanner class is pretty slow, and you shouldn't use it if the input could be potentially large. Use BufferedReader and StringTokenizer instead like in this code:

Code: Select all

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String line = reader.readLine();
            if (line == null) {
                // end of file reached
                break;
            }

            StringTokenizer tokenizer = new StringTokenizer(line);
            int num1 = Integer.parseInt(tokenizer.nextToken());
            int num2 = Integer.parseInt(tokenizer.nextToken());
...
        }
    }
}

And one more thing - apparently, % 2 and /= 2 operations are too slow in Java, I couldn't get rid of TLE with them. Use bitwise operators instead: x%2 == (x&1), x/2 == (x>>1).

[ithenewguyi]

great, thank you for your tips, it REALLY helps

but when i output something like
System.out.println(line+" "+biggest);

i got a Presentation Error, not sure why that happens...

[mf]

Judge probably expects you to omit any unnecessary spaces in the output even when they're present in the input.
i.e use System.out.println(num1+" "+num2+" "+biggest);

[ithenewguyi]

ahh, thank you very much!

[Codemonkey2000]

I keep getting time limit exceeded. I don't know how to make this code any more efficient. Am I missing something? :S

Code: Select all

uses crt;
var   i,j,max,x,tmp:longInt;

function foo(a:longInt):longInt;
var x,c:longInt;
begin
	x:=a;
	c:=1;
	while (x<>1) do
	begin
		if ((x mod 2) =0) then
			x:=x div 2
		else
			x:=x*3+1;
		c:=c+1;
	end;
	foo:=c;
end;

begin
	while not eof do
	begin
		readln(i,j);
		max:=0;
		write(i,' ',j);
		if i>j then
		begin
			tmp:=i;
			i:=j;
			j:=tmp;
		end;
		for x:=i to j do
		begin
			tmp:=foo(x);
			if tmp>max then
				max:=tmp;
		end;
		writeLn(' ',max);
	end;
end.

[scott1991]

this code is giving wa as well. I'm sure it's fine...Cheers for any help. Scott

Code: Select all

code now ac!

[Codemonkey2000]

I'm not getting WA, I'm getting Tile limit exceeded.

[Leonid]

I'm not getting WA, I'm getting Tile limit exceeded.

Use more efficient implementation

[Codemonkey2000]

I'm not getting WA, I'm getting Tile limit exceeded.

Use more efficient implementation

I know, but how can I make my code any more efficient? I posted the code above.

[CMG]

scott1991:

Code: Select all

for(o;o<=j;o++) 
{ 
    i=o; 
    while(i!=1) 
    { 
        i = (i&1)==0?(i>>1):(i*3+1);
        n++;
    }
}

Your limit didn't include j previously, and the inside of the while statement can be simplfied as shown.

Codemonkey2000: you should do something similar.

[scott1991]

Now i'm really confused for 1 and 10, it gives max cycle length as 67!!! the code now is:

Code: Select all

// 3n+1 - 100.cpp : Defines the entry point for the console application.
#include <iostream>

int main()
{
	int n=0,i,j,store=0,o,p,temp,f;
a:	
	scanf("%d%d",&o,&j);
	if (o==-1||j==-1)
	{return 0;}
	else
	{
	
		if(o>j)
		{temp=o;o=j;j=temp;f=1;}
		p=o;
	
		for(o;o<=j;o++) 
		{ 
			i=o; 
			while(i!=1) 
			{ 
				i = (i&1)==0?(i>>1):(i*3+1); 
				n++; 
			} 
		} 
			if(store<n)
			{store=n;}
			n=1;
		
		if (f==1)
		{temp=j;j=p;p=temp;f=0;}
		printf("%d %d %d\n",p,j,store);
		store=0;
		goto a;
	}
	return 0;
}

please healp!!!!

[CMG]

Code: Select all

      for(o;o<=j;o++) {
         n = 1;
         i = o;
         while(i!=1) {
            i = (i&1)==0?(i>>1):(i*3+1);
            n++; 
         }
         if(store<n) {
            store = n;
         }
      }

Your problem was when you changed from your previous code you took out the check if(store<n) from the for statement and forgot to reset n to 1 in the for statement as well, which was partly my fault since I closed the for loop statement in my previous post when I didn't mean to .

[scott1991]

that did help...but it is still a wrong answer...can anyone give a list of tests or something? cheers. scott

my code now stands thus:

Code: Select all

code now ac!!

[mf]

Try the input

Code: Select all

10 10
10 10

Your code outputs two different answers.

[scott1991]

lol...well thats odd...Well, now that's cleared up...the program works!!! Cheers guys!!! Your a great help. CMG-Thanks for your help...you've taught me something new(the ? sign) and MF- thanks for your time to spot something i wouldn't have unless i had cone through tonnes of inputs. Cheers once again!