## 100 - The 3n + 1 problem

Moderator: Board moderators

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

### 100: time exceeded

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
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: Why WA???

What was the problem number?
http://www.newton.0fees.net is enough! linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### Re: 100: time exceeded

http://online-judge.uva.es/board/viewto ... ?f=1&t=386

Solving for fun..

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

### Re: 100 : Wrong Answer

http://online-judge.uva.es/board/viewto ... ?f=1&t=386

Solving for fun..

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

### Re: 100

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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

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

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

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

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

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

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

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

### Re: 100

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

Code: Select all

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

public class Main {

final static int MAX = 1000001;
static int[] lista = new int[MAX];

public static void main(String[] args) {
String line;
int i,j,k;
int maximo;
lista = 1;
try{
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

### Re: 100

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