100 - The 3n + 1 problem

[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) {

[coder.tanvir]

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

[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]

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]

fiamma, use %ld for long int. Don't print a space at the end of a line.

[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]

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]

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]

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]

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

[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]

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]

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]

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]

Your straightforward solution is very slow. Read this thread for better solution. At least read post of metaphysis above yours.