100 - The 3n + 1 problem
Moderator: Board moderators
WA in 100!?
hi all, any help would be appreciated! I have tried long long, memoization, etc... i give up ![;)](./images/smilies/icon_wink.gif)
*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 */
![;)](./images/smilies/icon_wink.gif)
*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 */
Last edited by thesnikes on Sun Dec 14, 2003 5:59 pm, edited 1 time in total.
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
-
- New poster
- Posts: 9
- Joined: Tue Jan 06, 2004 7:33 am
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]
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]
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]
[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]
help needed
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]
[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]
Did that, but still WA ?junbin wrote: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.
![:(](./images/smilies/icon_frown.gif)
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]
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Virko:
You flip them to claculate the longest chain, but you have to output them in the order given in the input. So for inputthe correct answer is
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
Code: Select all
1 10 20
10 1 20
I tryed that too, but I still get WA ?little joey wrote:Virko:
You flip them to claculate the longest chain, but you have to output them in the order given in the input. So for inputthe correct answer isCode: Select all
1 10 10 1
Code: Select all
1 10 20 10 1 20
![:(](./images/smilies/icon_frown.gif)
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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.
[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.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein
-Albert Einstein