100 - The 3n + 1 problem

[brianfry713]

Test your code on the sample input given in the problem statement and see if it matches the sample output. On my computer, on input:
201 210
Your code prints
201 210 125
instead of the correct
201 210 89

[maged9182]

Okay so I've been trying to solve 3n+1 , code 100, to no avail.. Here's the code giving me the Runtime error

Code: Select all

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

public class Main{
	
	public static void main (String[]args) throws IOException{
		
		BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		StringTokenizer st = new StringTokenizer (br.readLine());

		
		while (st.hasMoreTokens()){
			

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if (b<a){
				int temp = a;
				a = b;
				b=temp;
				
			}
			
			int max =0;
			for (int i=a; i<=b; i++){
				
			 int c = execute(i);
			 if (c>max){
				 max=c;
			 }
			
			}
			//System.out.println(a + " " + b + " " + max + "\n");
			sb.append(a + " " + b + " " + max + "\n");
			st = new StringTokenizer (br.readLine());

			
		}
		
		System.out.print(sb);
		System.exit(0);
		
	}
	
	public static int execute (int x){
		int count =1;
		
		while (x!=1){
			if (x%2==0){
				x=x/2;
			}
			else{
				x= 3*x+1;
			}
			count++;
		}
		return count;
		
	}
	
}

And here's the one giving me wrong answer, i changed the looping condition and how I create the tokenizer that's all

Code: Select all

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

public class Main{
	
	public static void main (String[]args) throws IOException{
		
		BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		String line = "";

		
		while ((line=br.readLine())!=null){
			
			StringTokenizer st = new StringTokenizer (line);

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if (b<a){
				int temp = a;
				a = b;
				b=temp;
				
			}
			
			int max =0;
			for (int i=a; i<=b; i++){
				
			 int c = execute(i);
			 if (c>max){
				 max=c;
			 }
			
			}
			//System.out.println(a + " " + b + " " + max + "\n");
			sb.append(a + " " + b + " " + max + "\n");
			
		}
		
		System.out.print(sb);
		System.exit(0);
		
	}
	
	public static int execute (int x){
		int count =1;
		
		while (x!=1){
			if (x%2==0){
				x=x/2;
			}
			else{
				x= 3*x+1;
			}
			count++;
		}
		return count;
		
	}
	
}

Any help?

[brianfry713]

http://online-judge.uva.es/problemset/d ... .java.html

[bashie]

That doesn't help much. I'm getting this same "runtime error" issue. Not having problems resolving problem, but understanding how this thing compiles. I even tried deleting the "public" in the main from that example to no avail.

I'm pasting the code in the textbox, so it is a single file source code.
My classes do not belong to any package.
My class is named "Main" and has a static main method (tried with public as the example and without it).
The word "public" is not used in any place of my code, not for classes, methods or anything.
Using buffered i/o.

So why is it that my code generates a runtime error when tested locally (even with wrong input data) works fine? :S

[bashie]

ok, I found the thing that was giving the runtime error.

For every method you call, you should not use the implicit "this." you have to write it.

[invadrFlip]

What if i>j?

Nice catch brian. I hate it when they do that though. They should atleast show an example of this happening in the sample input.

[sulaimansust]

Here is my code . I couldn,t find any problem at this.. Someone help me please.....

/*100 - the 3n + 1 */
#include<stdio.h>
long int first, second;
main()
{
long int i, j, a;
int cycle, temp=0;
while(scanf("%ld%ld", &i, &j)==2)
{
first = i;
second = j;

cycle=0;
for(first; first<=second; first++)
{
a = first;
while(a!=1)
{
if(a%2==1)
{
a = 3 * a + 1;
++cycle;
continue;
}
else
{
a = a/2;
++cycle;
continue;
}
}
if(cycle>temp)
temp = cycle;
cycle = 0;
}
printf("%ld %ld %d\n",i, j, (temp+1));
temp=0;
}

return 0;

}

[brianfry713]

What if i>j?

[LucaLuca]

Hi everyone!
I can't understand what's wrong in my code (it gives me WA). Thank you!

Code: Select all

#include <iostream>
using std::cin;
using std::cout;

void scambio(int &n, int &m)
{
	int temp;
	temp=m;
	m=n;
	n=temp;
}

int main()
{
	int a,b;
	int max,length,num;

	while (cin >> a >> b)
		{
		max=0;

		if (a>b)
			scambio(a,b);

		for (int i=a;i<=b;i++)
			{
			num=i;
			length=1;
				while (num!=1)
					{
					if (num%2==0)
						num/=2;
					else
						//(num*=3)++;
						num=num*3+1;

					length++;
					}	
			
			if (max < length)
				max = length;

			}

		cout << a << " " << b << " " << max << "\n";
		}

	return 0;
}

P.S. I tried to remove the procedure scambio (maybe the controller doesn't support it) but nothing changed!

[brianfry713]

Input:

Code: Select all

1 10
10 1

Correct output:

Code: Select all

1 10 20
10 1 20

You can use swap(), but it won't fix your issue in this problem.

[LucaLuca]

Input:

Code: Select all

1 10
10 1

Correct output:

Code: Select all

1 10 20
10 1 20

You can use swap(), but it won't fix your issue in this problem.

I uses a procedure to put in the correct order the input...if a=10 and b=1 then with the procedure scambio a=1 and b=10 and the output becomes correct.

The output of the program has to be continuous or alternated with input?

My program does this for example:

INPUT:1 10
OUTPUT: 1 10 20
INPUT:10 1
OUTPUT: 1 10 20

[LucaLuca]

I changed like this but it doesn't work:

Code: Select all

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

void scambio(int &n, int &m)
{
	int temp;
	temp=m;
	m=n;
	n=temp;
}

int main()
{
	int a,b;
	int max,length,num;
	bool order=0;
	
	while (cin >> a >> b)
		{
		max=0;

		if (a>b)
           {
			scambio(a,b);
			order=1;
           }

		for (int i=a;i<=b;i++)
			{
			num=i;
			length=1;
				while (num!=1)
					{
					if (num%2==0)
						num/=2;
					else
						//(num*=3)++;
						num=num*3+1;

					length++;
					}	
			
			if (max < length)
				max = length;

			}
        if (order)
           scambio(a,b);
		cout << a << " " << b << " " << max << endl;
		}

	return 0;
}

I used again the procedure scambio and output becomes like you have said:

INPUT:

Code: Select all

1 10
10 1

OUTPUT

Code: Select all

1 10 20
10 1 20

Before it did:

INPUT:

Code: Select all

1 10
10 1

OUTPUT

Code: Select all

1 10 20
1 10 20

[brianfry713]

Try input:

Code: Select all

10 1
1 10

[renatov]

Here is a tip: in C, use long int for the main variable types and test these inputs/outputs:

Code: Select all

1 10
100 200
201 210
900 1000
1000 900
999999 999990

1 10 20
100 200 125
201 210 89
900 1000 174
1000 900 174
999999 999990 259

[hercules]

Hey,
This is 3n+1 problem.Here is my code.I got time limit exceed problem.I need help to fix the problem.

-------------------------------------
include <iostream>
#include <string>
#include <sstream>
#include<cstdio>
#include<climits>
using namespace std;

int main()
{

long unsigned int number1,number2,temp,number,i,m,big,c;
freopen("100.in","r",stdin);
cin >> number1>>number2;
cout<<number1<<number2;
//cout << number <<;

if (number1>number2){
temp=number1;
number1=number2;
number2=temp;
}
big=0;
for (i=number1;i<=number2;i++)
{

c=1;
m=i;
do
{
if(m%2==0)
{


m=m/2;
//cout<<number1;
c++;}
else
{
m=3*m+1;
//cout<<number1;
c++;
}
} while(m!=1);
if(c>big)
big=c;
}
cout<<big;
return 0;
}