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: 100 - The 3n + 1 problem

Post by brianfry713 » Thu Jan 15, 2015 10:32 pm

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

Your code is only processing the first pair of integers. You need to continue to read until EOF.
Change:
cin >> i >> j;
to:
while(cin >> i >> j) {
Check input and AC output for thousands of problems on uDebug!

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

Re: 100 - The 3n + 1 problem

Post by coder.tanvir » Fri Mar 20, 2015 8:33 am

how to reduce the run time ?? i get accepted 0.690s

fiamma
New poster
Posts: 1
Joined: Fri Mar 20, 2015 6:50 pm

Re: 100 - The 3n + 1 problem

Post by fiamma » Fri Mar 20, 2015 7:01 pm

i got time exceeded error, anyone know how can i reduce this time?

Code: Select all

#include <stdio.h>
void swap( long int* x, long int* y)
{
   long int temp;
 
   temp = *x;
   *x    = *y;
   *y    = temp;
}
int main(){
	long int i,j, act_value, aux, count, max;
	while (scanf("%d %d" , &i, &j) != EOF){	
		max=0;
		printf("%d %d", i, j);
		if (i>j) swap (&i, &j);
		for (act_value=i;act_value<=j; act_value++){
			aux= act_value;
			count=1;
			while(aux!=1){
				if(aux%2 ==1) aux =(aux*3)+1;
				else aux=aux/2;
				count++;
			}
			if (count>= max) max =count;
			}
			printf(" %d \n",max);
			}	 
				
	

return (0);}

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

Re: 100 - The 3n + 1 problem

Post by coder.tanvir » Fri Mar 20, 2015 10:34 pm

write another function who can calculate the max length , then just call from main . dont know why this way reduce time , its work for me.

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

Re: 100 - The 3n + 1 problem

Post by brianfry713 » Tue Mar 31, 2015 12:30 am

fiamma, use %ld for long int. Don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!

dipu008
New poster
Posts: 1
Joined: Sun Jun 28, 2015 10:47 am

Re: 100 - The 3n + 1 problem

Post by dipu008 » Sun Jun 28, 2015 10:52 am

I have posted this code and got wrong answer. What is the problem here? Thanks in advance.
The code is in ANSI C

Code: Select all


#include <stdio.h>

int f(int i);

int main()
{
    int num1, num2, n, i, j, h;
    while(scanf("%d %d", &num1, &num2) == 2){
        n = 0;
        for(i=num1; i<=num2; i++){
            j = f(i);
            if(n < j) {
                n = j;
                h = i;
            }
        }
        printf("%d %d %d\n", num1, num2, n+1);
    }
    return 0;
}

int f(int n)
{
    int i;
    for(i=0; n!=1;i++){
            if(n%2){
                n = 3 * n + 1;
            }
            else if(!(n%2)){
                n = n / 2;
            }
    }

    return i;
}

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 100 - The 3n + 1 problem

Post by apcastelein » Wed Jul 01, 2015 4:00 am

Your f function isn't working properly. If 1 is inputted the output should be 1 however in your case the output is 0.

TamceJoe
New poster
Posts: 3
Joined: Wed Sep 16, 2015 4:23 pm

Re: 100 - The 3n + 1 problem

Post by TamceJoe » Thu Sep 17, 2015 3:44 pm

i got a problem... i test my program on my pc and it works perfectly well but i got Wrong Answer online.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.

Code: Select all

#include <cstdio>
#include <queue>
#include <map>

using namespace std;

typedef unsigned long int_t;

map<int_t, int_t> record;

void calc(int_t);

int main()
{
	int_t a = 0, b = 0, m = 0;
	int_t l = 0, r = 0;
	bool first = true;
	while(scanf("%ld%ld", &l, &r) == 2)
	{
		if(l > r) a = r, b = l;
		else a = l, b = r;
		for(int_t i = a; i <= b; ++i)
			calc(i);
		m = 0;
		for(int_t i = a; i <= b; ++i)
			m = m > record[i] ? m : record[i];
		if(first) printf("%ld %ld %ld", l, r, m + 1);
		else printf("\n%ld %ld %ld", l, r, m + 1);
		first = false;
	}
	return 0;
}

void calc(int_t t)
{
	queue<int_t> a;
	while(t != 1)
	{
		if(record[t] != 0) break;
		a.push(t);
		if(t % 2 == 0)
			t /= 2;
		else
			t = 3 * t + 1;
	}
	int_t base = record[t];
	while(!a.empty())
	{
		if(record[a.front()] != 0) break;
		record[a.front()] = a.size() + base;
		a.pop();
	}
}

TamceJoe
New poster
Posts: 3
Joined: Wed Sep 16, 2015 4:23 pm

Re: 100 - The 3n + 1 problem

Post by TamceJoe » Thu Sep 17, 2015 4:51 pm

TamceJoe wrote:i got a problem... i test my program on my pc and it works perfectly well but i got Wrong Answer online.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.

Code: Select all

#include <cstdio>
#include <queue>
#include <map>

using namespace std;

typedef unsigned long int_t;

map<int_t, int_t> record;

void calc(int_t);

int main()
{
	int_t a = 0, b = 0, m = 0;
	int_t l = 0, r = 0;
	bool first = true;
	while(scanf("%ld%ld", &l, &r) == 2)
	{
		if(l > r) a = r, b = l;
		else a = l, b = r;
		for(int_t i = a; i <= b; ++i)
			calc(i);
		m = 0;
		for(int_t i = a; i <= b; ++i)
			m = m > record[i] ? m : record[i];
		if(first) printf("%ld %ld %ld", l, r, m + 1);
		else printf("\n%ld %ld %ld", l, r, m + 1);
		first = false;
	}
	return 0;
}

void calc(int_t t)
{
	queue<int_t> a;
	while(t != 1)
	{
		if(record[t] != 0) break;
		a.push(t);
		if(t % 2 == 0)
			t /= 2;
		else
			t = 3 * t + 1;
	}
	int_t base = record[t];
	while(!a.empty())
	{
		if(record[a.front()] != 0) break;
		record[a.front()] = a.size() + base;
		a.pop();
	}
}
oh i got my solution accepted.
i thought there is no new line at the end of the output because the output on udebug does not show a new line

TamceJoe
New poster
Posts: 3
Joined: Wed Sep 16, 2015 4:23 pm

Re: 100 - The 3n + 1 problem

Post by TamceJoe » Thu Sep 17, 2015 4:52 pm

and use queue & map cost about 0.7s but do the calculate every time only cost 0.2s
xd

UvaPitu
New poster
Posts: 1
Joined: Mon Apr 11, 2016 1:57 am

Re: 100 - The 3n + 1 problem

Post by UvaPitu » Mon Apr 11, 2016 2:30 am

I am trying to submit my own version of The 3n+1 problem but i get the same result: Runtime Error. I edited many times my code but i am still getting this error and I don't know the reason. I hope you can help me, what i can do to get an AC.

I write my last edited code in the following lines:

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args)
    {
        new Main().run();
    }
    
    long Fef(long x)
    {
        long cicles = 0;
        long  temp = x;
        while (temp != 1)
        {
            if (temp % 2 == 0)
            {
                temp = temp /2;
                cicles++;
            }
            else
            {
                temp = 3 * temp + 1;
                temp = temp / 2;
                cicles = cicles + 2;
            }
        }
        cicles++;
        return cicles;
    }
    long MaxF(long from, long to)
    {
        long maximum = -1;
        for (long i = from; i <= to; i++)
        {
            long result = Fef(i);
            if (result > maximum)
                maximum = result;
        }
        return maximum;
    }
    private final long MAX = 1000000; // the maximum value accepted

    public void run()
    {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer idata;
	String line = null;
	try {
		line = br.readLine();
	        long from_value = 0;
	        long to_value = 0;
	
		while ( line != null ) 
		{
		    idata = new StringTokenizer(line);

		    while(idata.hasMoreTokens())
		    {
			    	if( from_value <= 0 && idata.hasMoreTokens() )
			    		from_value = Long.parseLong(idata.nextToken());
			    	if( to_value <= 0 && idata.hasMoreTokens() )
			    		to_value = Long.parseLong(idata.nextToken());
			    	if( from_value > 0 && to_value > 0 )
			    	{
			            long from, to;
			            if (from_value > to_value)
			            {
			                from = to_value;
			                to = from_value;
			            }
			            else
			            {
			                from = from_value;
			                to = to_value;
			            }
			            if( from > 0 && to < MAX)
			            	System.out.printf("%d %d %d\n", from_value, to_value, MaxF(from, to));
			            from_value = -1;
			            to_value = -1;
			    	}
			    }		    
			    line = br.readLine();
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
    }

}
I will appreciate any comments or guidelines. Thanks!

selection989
New poster
Posts: 1
Joined: Fri May 06, 2016 5:34 pm

Re: 100 - The 3n + 1 problem

Post by selection989 » Fri May 06, 2016 6:16 pm

Hi there,

I am having trouble getting it to work in python. I keep getting a time limit exceeded. Any suggestions would be much appreciated. Here is my code:
import sys
from sys import stdin

def main():

for line in stdin:
curr_line=line.split()
if curr_line[0]<=curr_line[1]:
min_num=int(curr_line[0])
max_num=int(curr_line[1])
else:
max_num=int(curr_line[0])
min_num=int(curr_line[1])
maxCycleLength =0
for curr_num in range(min_num,max_num+1):
currCycleLength =1
while curr_num!=1:
currCycleLength +=1
if curr_num%2==0:
curr_num=curr_num/2
else:
curr_num=3*curr_num+1
maxCycleLength=max(currCycleLength,maxCycleLength)
print(curr_line[0],curr_line[1],maxCycleLength,sep=" ")

return
main()
sys.exit()

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 100 - The 3n + 1 problem

Post by metaphysis » Tue Jun 14, 2016 4:24 pm

Try input:

Code: Select all

999999 1
To avoid TLE, you should use memoization to store the results calculated, use it directly instead of calculating it again.
For example, n = 21, the sequences below produced:

Code: Select all

21 64 32 16 8 4 2 1
so, when you got the steps of 21, you can calculate the steps of 64 by add 1 step.

pk__modi
New poster
Posts: 1
Joined: Mon Aug 01, 2016 7:52 pm

Re: 100 - The 3n + 1 problem

Post by pk__modi » Mon Aug 01, 2016 8:25 pm

someone plz help why am i getting TLE:

#include<iostream>
#include<cstdio>
#include<cstdlib>

#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)

int main()
{
int i,j,min,max,maximum=0;
while(scanf("%d%d",&i,&j))
{ max=max(i,j);
min=min(i,j);
maximum=0;
while(min<=max)
{
int count=1;
int k=min;
while(k>1)
{
k=(k%2)?(3*k+ 1):(k>>1);

count++;
}

min++;
if(count>maximum) maximum=count;

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

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 100 - The 3n + 1 problem

Post by lighted » Sun Mar 12, 2017 3:27 pm

Your straightforward solution is very slow. Read this thread for better solution. At least read post of metaphysis above yours.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 1 (100-199)”