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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 100 - The 3n + 1 problem

Post by lighted »

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)”