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

brock
New poster
Posts: 2
Joined: Fri Dec 26, 2008 3:06 pm

100: time exceeded

Post by brock » Sat Jan 03, 2009 6:13 pm

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

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: Why WA???

Post by newton » Mon Jan 05, 2009 5:16 pm

What was the problem number?

User avatar
linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: 100: time exceeded

Post by linux » Wed Jan 07, 2009 1:37 pm

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.
Solving for fun..

User avatar
linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: 100 : Wrong Answer

Post by linux » Wed Jan 07, 2009 1:43 pm

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.
Solving for fun..

andy74139
New poster
Posts: 1
Joined: Sat Jan 10, 2009 3:28 am

Re: 100

Post by andy74139 » Sat Jan 10, 2009 3:35 am

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 100

Post by helloneo » Sat Jan 10, 2009 6:48 am


Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

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

Post by Obaida » Mon Feb 09, 2009 5:23 am

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. :D

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 :oops: :oops:
So any 1 help me to figure out my bug i'll be thank full. :oops:
Last edited by Obaida on Mon Feb 09, 2009 10:27 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by mf » Mon Feb 09, 2009 9:02 am

Read posts on the first page of this thread.
Obaida wrote:First of all m sorry for my post i can't even check with large input cause my compiler didn't support long long :oops: :oops:
Then why don't you dump it and get one, that supports long long?

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

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

Post by Obaida » Mon Feb 09, 2009 10:14 am

I was supposed to print that 2 input after scaning why i forgot i don't know!!!! :o
Any way thank you... I got acc in 0.070sec hope to optimize it.. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

Ariens
New poster
Posts: 2
Joined: Sat Feb 14, 2009 1:16 am

Re: 100

Post by Ariens » Sat Feb 14, 2009 1:17 am

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

	}
}
Last edited by Ariens on Sat Feb 14, 2009 7:22 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 100

Post by mf » Sat Feb 14, 2009 2:55 am

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

Ariens
New poster
Posts: 2
Joined: Sat Feb 14, 2009 1:16 am

Re: 100

Post by Ariens » Sat Feb 14, 2009 7:20 pm

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

Thanks

rafaelj
New poster
Posts: 1
Joined: Tue Feb 24, 2009 10:28 pm

Re: 100

Post by rafaelj » Tue Feb 24, 2009 10:33 pm

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 100

Post by Obaida » Wed Mar 11, 2009 10:06 am

You should try this:
Input:

Code: Select all

20 10
Output:

Code: Select all

20 10 21
try_try_try_try_&&&_try@try.com
This may be the address of success.

kayanat
New poster
Posts: 1
Joined: Mon Mar 09, 2009 9:40 am

Re: 100 Runtime Error

Post by kayanat » Fri Mar 13, 2009 7:17 am

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?!

Post Reply

Return to “Volume 1 (100-199)”