100 - The 3n + 1 problem
Moderator: Board moderators
laughing all the way...
Okay.
Now it compiles (because I forgot that stupid return statement)
Now it reports TIME LIMIT EXCEEDED.
Is my program that inefficient?
Now it compiles (because I forgot that stupid return statement)
Now it reports TIME LIMIT EXCEEDED.
Is my program that inefficient?
Wow - I bow to those who solved this deceivingly simple prob
Okay.
I narrowed down what my program was doing.
Geez.
It's a simple problem that's cursed website owners and commercial enterprises.
I found a test case number (by putting in ranges of test inputs) which I wont reveal here, unless asked of course, that when I put in that number as input, my program would run on forever.
It's because the number would eventually lead to such a high number in 3N+1, that it would overflow and become negative - thus never reaching a solution.
Geez.
It reminds me of the old news story (help me out if you can remember) where a guy was buying products from a store online. He was putting in a number so big (I dont remember if it was quantity or price), he would be getting products delivered to his door along with a sizeable check (because the price turned out to be negative, he was owed money according to the system).
Basically an employee of the company noticed this and asked (why the **** are we shipping a product to this guy along with a check?)
Ugh!
Back to the drawing board.
I narrowed down what my program was doing.
Geez.
It's a simple problem that's cursed website owners and commercial enterprises.
I found a test case number (by putting in ranges of test inputs) which I wont reveal here, unless asked of course, that when I put in that number as input, my program would run on forever.
It's because the number would eventually lead to such a high number in 3N+1, that it would overflow and become negative - thus never reaching a solution.
Geez.
It reminds me of the old news story (help me out if you can remember) where a guy was buying products from a store online. He was putting in a number so big (I dont remember if it was quantity or price), he would be getting products delivered to his door along with a sizeable check (because the price turned out to be negative, he was owed money according to the system).
Basically an employee of the company noticed this and asked (why the **** are we shipping a product to this guy along with a check?)
Ugh!
Back to the drawing board.
Well, there's no magical number. From the look of you code (I haven't tested) your program should fail on input like
Code: Select all
10 100
100 10
10 100
100 Compile error 6 times... Help!!
my code:
-------------------------------------------------------------------------------------
import java.util.*;
class Main
{
static int Begin(int a, int b, int flag)
{
int count = 0, cyclelength = 0, c=0;
int temp = b;
if (a>b){
b=a;
a=temp;}
for (int i=a;i<=b;i++,count=0)
{
c=i;
while(c!=1)
{
count++;
if (c%2==1)
c=3*c+1;
else
c=c/2;
}
if (count>cyclelength)
{
cyclelength=count+1;
}
}
return cyclelength;
}
public static void main(String[] args)
{
int flag = 0;
int i=0;
String[] storedline = new String[1000];
Main TryOne = new Main();
Scanner scanner = new Scanner(System.in);
while (flag!=1)
{
String getinput = scanner.nextLine();
if (!(getinput.equals("")))
{
Scanner scanner1 = new Scanner(getinput);
int a = scanner1.nextInt();
int b = scanner1.nextInt();
int temp = TryOne.Begin(a,b,flag);
storedline = a + " " + b + " " + temp;
i++;
}
else
flag++;
}
for (int j=0; j<i; j++)
System.out.println(storedline[j]);
}
}
compile error!! i read the sticky, made amendemnts and still get CE... i suspected it is becos of the Scanner class i used... any help??
-------------------------------------------------------------------------------------
import java.util.*;
class Main
{
static int Begin(int a, int b, int flag)
{
int count = 0, cyclelength = 0, c=0;
int temp = b;
if (a>b){
b=a;
a=temp;}
for (int i=a;i<=b;i++,count=0)
{
c=i;
while(c!=1)
{
count++;
if (c%2==1)
c=3*c+1;
else
c=c/2;
}
if (count>cyclelength)
{
cyclelength=count+1;
}
}
return cyclelength;
}
public static void main(String[] args)
{
int flag = 0;
int i=0;
String[] storedline = new String[1000];
Main TryOne = new Main();
Scanner scanner = new Scanner(System.in);
while (flag!=1)
{
String getinput = scanner.nextLine();
if (!(getinput.equals("")))
{
Scanner scanner1 = new Scanner(getinput);
int a = scanner1.nextInt();
int b = scanner1.nextInt();
int temp = TryOne.Begin(a,b,flag);
storedline = a + " " + b + " " + temp;
i++;
}
else
flag++;
}
for (int j=0; j<i; j++)
System.out.println(storedline[j]);
}
}
compile error!! i read the sticky, made amendemnts and still get CE... i suspected it is becos of the Scanner class i used... any help??
.....Life is just like a LM741........
I'm getting WA and i can't find the problem. It works just fine when i test it.
Can anyone help me?
Code: Select all
#include <stdio.h>
int main(void)
{
long x, a, b, n;
int m, w, c;
while(scanf("%ld %ld", &a, &b) == 2){
if (a < b)
w = 1;
else
w = -1;
m = 0;
x = a;
while (x != b){
n = x;
c = 1;
while (n > 1){
if (n%2)
n = n*3 + 1;
else
n /= 2;
c++;
}
if (c > m)
m = c;
x +=w;
}
printf("%li %li %d\n", a, b, m);
}
return 0;
}
InputYou should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
Code: Select all
22 22
21 22
Code: Select all
22 22 16
21 22 16