100 - The 3n + 1 problem

[deddy one]

http://acm.uva.es/problemset/data/p100.c.html

[thesnikes]

hi all, any help would be appreciated! I have tried long long, memoization, etc... i give up

*never mind*... read the sticky.
/* @BEGIN_OF_SOURCE_CODE */
#include <iostream>
using namespace std;

long docycle (long x)
{
long i=1;

while (x!=1)
{
if (x%2==0)
x=x/2;
else
{
i++;
x=(x*3)+1;
}
i++;
}
return i;
}


int main()
{
long a,b,x,maxX,i;
while (cin >> a >>b)
{
maxX=0;
for (i=a;i<=b;i++)
{
x=docycle(i);
if (x > maxX)
maxX=x;
}
cout << a << ' ' << b << ' ' << maxX << endl;
}

return 0;
}

/* @END_OF_SOURCE_CODE */

[Almost Human]

why don't you read the sticky post about problem 100 first ?

the problem doesn't declare that a should be less than b, and I believe you didn't handle that in your source code.

I hope this would help you.

[thesnikes]

I did read the sticky but I didn't realize that they meant a might be less than b and that I should handle that case

thanks.

[nobody10_ca]

I got AD on when using submit-o-matic
this is my first time using the online judege system, anything I can do to not get AD again?
also, 1000000 is too big for int and long (when calculating cycle length), anything I can do to calculate integers above 10^10?
btw, I use C++
[cpp]#include <iostream>
#include <fstream>


using namespace std;
int func(long n);
int main()
{

long a, b, highest;

while (cin>>a>>b)
{
cout<<a<<" "<<b<<" ";
if (a>=b)
{
long temp=b;
b=a;
a=temp;
}
highest=func(a);
for (long i=a+1; i<=b; i++)
{
if (func(i) > highest)
highest=func(i);
}
cout<<highest<<endl;
}
return 0;
}

int func(long n)
{
long total=1;

while (n!=1)
{
if (n%2==1)
n=3*n+1;
else
n=n/2;
total++;
}
return total;
}[/cpp]

[Virko]

I got WA ??? Could anyone tell me what's wrong ?

[pascal]Var N,K,J,E,C,Max : LongInt;
OK : Boolean;

Begin
While Not Eof Do
Begin
Max := 0;
Read(N,K);
If (N = 0) Or (K = 0) Then Exit;
If K > N Then
Begin
For E := N To K Do
Begin
J := E;
While (C < 1000000) And (OK = False) And (J > 0) Do
Begin
If Odd(J) = True Then J := J * 3 + 1 Else J := J Div 2;
Inc(C);
If (J = 1) Then OK := True;
End;
C := C + 1;
If C > Max Then Max := C;
C := 0;
OK := False;
End;
WriteLn(N,' ',K,' ',Max);
End;
End;
End.[/pascal]

[junbin]

I think after you read the 2 numbers, you're supposed to flip them around so that you loop from the smaller one to the bigger one.

[nightdog]

i keep getting Time Exceeded, can anyone enlighten me on how to make the algorithm faster?

[c]
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

struct data {
float i,j,result;
struct data *next;
};

int main() {
float swap,i, j,input,result, maxcycle;
struct data *start=NULL, *cur,*prev;
while((scanf("%f %f", &i, &j)) != EOF) {
float maxcycle = 0;
if(!((cur) = (struct data *) malloc(sizeof(struct data)))) {
perror("malloc");
exit(1);
}
if(!start) {
start= cur;
start->next = NULL;
prev = start;
}
cur->i=i; cur->j = j;
if(i > j) {
long swap = i;i = j; j= swap;
}
for(input=i;input<=j;input++) {
float count=1,n=input;
while(n != 1) {
count++;
if((n/2) != floorf(n/2))
n = (3*n)+1;
else
n /= 2;

}
if(count > maxcycle)
maxcycle =count;
}
cur->result=maxcycle;
prev->next= cur;
cur->next = NULL;
prev = cur;
}

for(cur=start; cur;cur=cur->next) {
printf("%.0f %.0f %.0f\n", cur->i, cur->j, cur->result);
}
exit(0);
}

[/c]

[Virko]

I think after you read the 2 numbers, you're supposed to flip them around so that you loop from the smaller one to the bigger one.

Did that, but still WA ?

Here is code:

[pascal]Var N,K,J,E,C,TN,TK,Max : LongInt;
OK : Boolean;

Begin
Max := 0;
Read(TN,TK);
If (TN = 0) Or (TK = 0) Then Exit;
If (TK < 1000000) And (TN < 1000000) Then
Begin
N := TN;
K := TK;
If TN > TK Then Begin N := TK; K := TN; End;
Write(N,' ',K,' ');
For E := N To K Do
Begin
J := E;
While (C < 1000000) And (J >= 1) And (OK = False) Do
Begin
Inc(C);
If J > 1 Then If Odd(J) = True Then J := J * 3 + 1 Else J := J Div 2;
If (J = 1) Then OK := True;
End;
If C > 1 Then C := C + 1;
If C > Max Then Max := C;
C := 0;
OK := False;
End;
WriteLn(Max);
End;
End.[/pascal]

[little joey]

Virko:
You flip them to claculate the longest chain, but you have to output them in the order given in the input. So for input

Code: Select all

1 10
10 1

the correct answer is

Code: Select all

1 10 20
10 1 20

[Virko]

Virko:
You flip them to claculate the longest chain, but you have to output them in the order given in the input. So for input

Code: Select all

1 10
10 1

the correct answer is

Code: Select all

1 10 20
10 1 20

I tryed that too, but I still get WA ?

[little joey]

Your code only reads two numbers and then stops (unlike the code you previously posted). Also you don't initialise the integer C the first time around the loop.
Just a couple of observations; there can be still more errors.

[Virko]

It doesn't work if I loop also, and all of my testing outputs are OK ?

[little joey]

PM me your most recent program, and I'll have a look at it.

[fangs404]

I've been having a problem submitting this, also. My output seems correct. What could I be doing wrong?

[java]
import java.io.*;

class Main
{
public static void main(String[] args)
{
Main puzzle = new Main();
int highest = 0, a = 0, b = 0, temp = 0;
String nums, num1, num2;
boolean switched = false;

while((nums = puzzle.ReadLn(1024)) != null && nums.length() > 1)
{
num1 = nums.substring(0, nums.indexOf(32));
num2 = nums.substring(nums.indexOf(32) + 1, nums.length() - 1);
a = Integer.parseInt(num1);
b = Integer.parseInt(num2);

if(a > b)
{
temp = a;
a = b;
b = temp;
switched = true;
}

for(int q = a; q <= b; q++)
if(puzzle.returnCount(q) > highest)
highest = puzzle.returnCount(q);

if(!switched)
System.out.println(a + " " + b + " " + highest);
else
System.out.println(b + " " + a + " " + highest);

highest = 0;
switched = false;
}
}

public int returnCount(int num)
{
int temp = num, count = 1;

while(temp != 1)
{
if(temp % 2 == 0)
temp /= 2;
else
temp = temp * 3 + 1;

count++;
}

return count;
}

public String ReadLn(int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();

if ((car < 0) || (car == '\n'))
break;

lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0))
return (null);

return (new String (lin, 0, lg));
}
}
[/java]

Any ideas? Thanks for any help.