100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: If you get WA in problem 100, read me before post!

Post by 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
Check input and AC output for thousands of problems on uDebug!

maged9182
New poster
Posts: 1
Joined: Wed Jun 27, 2012 7:02 am

Runtime error and WA on 100 (3n+1)

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Runtime error and WA on 100 (3n+1)

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

bashie
New poster
Posts: 2
Joined: Fri Jul 13, 2012 10:08 pm

Re: Runtime error and WA on 100 (3n+1)

Post by 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
New poster
Posts: 2
Joined: Fri Jul 13, 2012 10:08 pm

Re: Runtime error and WA on 100 (3n+1)

Post by 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
New poster
Posts: 8
Joined: Fri Aug 10, 2012 7:48 am

Re: General Submission Q + Wrong Answer->100 The 3n + 1 prob

Post by 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
New poster
Posts: 4
Joined: Fri Jul 27, 2012 1:53 pm

Re: If you get WA in problem 100, read me before post!

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: If you get WA in problem 100, read me before post!

Post by brianfry713 »

What if i>j?
Check input and AC output for thousands of problems on uDebug!

LucaLuca
New poster
Posts: 3
Joined: Fri Aug 31, 2012 5:25 pm

Re: If you get WA in problem 100, read me before post!

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: If you get WA in problem 100, read me before post!

Post by 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.
Check input and AC output for thousands of problems on uDebug!

LucaLuca
New poster
Posts: 3
Joined: Fri Aug 31, 2012 5:25 pm

Re: If you get WA in problem 100, read me before post!

Post by LucaLuca »

brianfry713 wrote: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
New poster
Posts: 3
Joined: Fri Aug 31, 2012 5:25 pm

Re: If you get WA in problem 100, read me before post!

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: If you get WA in problem 100, read me before post!

Post by brianfry713 »

Try input:

Code: Select all

10 1
1 10
Check input and AC output for thousands of problems on uDebug!

renatov
New poster
Posts: 20
Joined: Fri Sep 21, 2012 6:33 am

Re: If you get WA in problem 100, read me before post!

Post by 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
New poster
Posts: 2
Joined: Thu Oct 25, 2012 8:23 pm

time limit excede problem

Post by 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;
}

Post Reply

Return to “Volume 1 (100-199)”