100 - The 3n + 1 problem

[brock]

how can i reduce the time in the 3n+1 problem!!!!

Code: Select all

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int test=0;
	long int x,y,count,i,old;
	long long int j;
//	double j;
	vector<long int>v;
	while(cin>>x>>y){
		if(x>y){
			swap(x,y);
			test=1;
		}
		for(i=x;i<=y;i++){
		//	cout<<i<<endl;
			count=0;
			j=i;
			while(j!=1){
				//cout<<j<<endl;	
				if(j%2==1){
					j=3*j+1;
				}else{
					j=j/2;
				}
				if(j==0){
					break;
				}	
				count++;
			}
			if(i==x){
				old=count;
			}else{	
				if(count>old){
					old=count;
				}
			}		
		}
		if(test==0){
		cout<<x<<" "<<y<<" "<<++old<<endl;
		}else{
			cout<<y<<" "<<x<<" "<<++old<<endl;
		}	
		old=0;
		count=0;
		
	}	
		return 0;
}							

[newton]

What was the problem number?

[linux]

It might help you:
http://online-judge.uva.es/board/viewto ... ?f=1&t=386
http://www.google.com/search?q=acm.uva. ... =firefox-a

Don't open new threads when the topic already exists in older threads.

[linux]

It might help you:
http://online-judge.uva.es/board/viewto ... ?f=1&t=386
http://www.google.com/search?q=acm.uva. ... =firefox-a

Don't open new threads when the topic already exists in older threads.

[andy74139]

Does anyone can look at my code and tell me what the problem? I keep getting WA.

Code: Select all

#include <stdio.h>

int main() {
    int length, i, large, x, min, max, swap;
    
    while(scanf("%d", &min) == 1){
          scanf("%d", &max);
          large = 2;
          if(min>max){
              i = min;
              min = max;
              max = i;
              swap = 1;
          }else swap = 0;
          
          for(i=min; i<=max; i++){
              length = 1;
              x=i;
              while(x != 1){
                    if(x%2==0) x /= 2;
                    else x = 3*x + 1;
                    length++;
              }
              
              if(length > large) large = length;
          }
          
          if(swap) printf("%d %d %d\n", max, min, large);
          else printf("%d %d %d\n", min, max, large);
    }

    return 0;
}

Thanks.

[helloneo]

See mf's post right here

http://acm.uva.es/board/viewtopic.php?t ... =30#p99157

[Obaida]

Some 1 plz help me figure out my bug...
I i can figure it out then it can be done more firstly using pre-calculation.

Code: Select all

removed... thanks to mf

First of all m sorry for my post i can't even check with large input cause my compiler didn't support long long
So any 1 help me to figure out my bug i'll be thank full.

[mf]

Read posts on the first page of this thread.

First of all m sorry for my post i can't even check with large input cause my compiler didn't support long long

Then why don't you dump it and get one, that supports long long?

[Obaida]

I was supposed to print that 2 input after scaning why i forgot i don't know!!!!
Any way thank you... I got acc in 0.070sec hope to optimize it..

[Ariens]

Hi, I just got this problem accepted in C++ but with java it always TLEs

Code: Select all

import java.util.Scanner;

class Main {
	
	static int cycleLenght(int i) {

	}
	
	public static void main (String [] args)
	{

	}
}

[mf]

Use BufferedReader, and i & 1 instead of i % 2.

[Ariens]

i & 1 and changing the cycleLenght method to final was enough.

Thanks

[rafaelj]

Man, i don't know why I am getting WA. Could anybody please help me?

Code: Select all

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

public class Main {

	final static int MAX = 1000001;
	static int[] lista = new int[MAX];
	
	public static void main(String[] args) {
		BufferedReader inReader = new  BufferedReader(new InputStreamReader(System.in));
		String line;
		int i,j,k;
		int maximo;
		lista[1] = 1;
		try{
			while((line = inReader.readLine()) != null){
				StringTokenizer st = new StringTokenizer(line);
				if (st.hasMoreTokens()){
					i = Integer.parseInt(st.nextToken());
					j = Integer.parseInt(st.nextToken());
					if (i>j){
						k=i; i=j; j=k;
					}
					if (i<0) i=0; 
					
					if (j<0) j=0;
					
					maximo = 0;
					
					for(k = i; k <= j; k++){
			        	if(lista[k] == 0)
			            	lista[k] = count(k);
			            maximo = ((maximo > lista[k])? maximo : lista[k]);
			        }
					System.out.println(line.trim() + " " + maximo);
				}else System.exit(0);
			}	
		}
		catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static int count(int n){
		if(n <= 0)
	        return 0;
	    
	    if(n >= MAX){
	    	
	        int temp = 0;
	        while(n >= MAX){
	            if((n%2) == 0)
	                n = n * 3 + 1;
	            else
	                n /= 2;
	            
	            temp++;
	        }
	        return count(n) + temp;
	    }
		
		if (lista[n] == 0){
			if(n%2 == 0)
				lista[n] = count(n / 2) + 1;
	        else
	        	lista[n] = count(n * 3 + 1) + 1;
		}
		return (lista[n]);
	}
}

Tks!

[Obaida]

You should try this:
Input:

Code: Select all

20 10

Output:

Code: Select all

20 10 21

[kayanat]

What Java download do I need in order to upload pictures to Myspace? Lately I haven't been able to upload any pictures. Every time I click the 'upload' button, a screen pops up saying that I need to download Java and then it automatically takes me to a site called Java SE Downloads. The thing is, I don't know which one to download! Halpp?!