100 - The 3n + 1 problem
Moderator: Board moderators
Thanks Per for confirming the case. I was in a little doubt about cout and scanf. I have been said that, if you use stdio and iostraem together, they for the synchronizing problem they may not work together(thats why I used the word "may"
). But, now I see, it's just the opposite. Thanks again for the clarification.
"Everything should be made simple, but not always simpler"
I get WA, but I'm not sure why. I account for i > j and use longs so there's no overflow.
[java]import java.io.*;
import java.util.*;
class Main
{
public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}
static void Begin()
{
long i, j, max, count, k;
String in, out = "";
StringTokenizer tok;
long[] array = new long[1000000];
in = ReadLn(20);
while (in != null)
{
in = in.trim();
tok = new StringTokenizer(in);
i = Integer.parseInt(tok.nextToken());
j = Integer.parseInt(tok.nextToken());
out += i + " " + j + " ";
if (i > j)
{
k = i;
i = j;
j = k;
}
max = 0;
for (i = i; i <= j; i++)
{
k = i;
count = 1;
while (k != 1)
{
if (k % 2 == 0)
{
k /= 2;
count++;
}
else
{
k = k * 3 + 1;
count++;
}
if (k < 1000000 && array[(int)k] != 0)
{
count += array[(int)k] - 1;
break;
}
}
if (array[(int)i] == 0)
array[(int)i] = count;
if (count > max)
max = count;
}
out += max + "\n";
in = ReadLn(20);
}
System.out.print(out);
}
static 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]
[java]import java.io.*;
import java.util.*;
class Main
{
public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}
static void Begin()
{
long i, j, max, count, k;
String in, out = "";
StringTokenizer tok;
long[] array = new long[1000000];
in = ReadLn(20);
while (in != null)
{
in = in.trim();
tok = new StringTokenizer(in);
i = Integer.parseInt(tok.nextToken());
j = Integer.parseInt(tok.nextToken());
out += i + " " + j + " ";
if (i > j)
{
k = i;
i = j;
j = k;
}
max = 0;
for (i = i; i <= j; i++)
{
k = i;
count = 1;
while (k != 1)
{
if (k % 2 == 0)
{
k /= 2;
count++;
}
else
{
k = k * 3 + 1;
count++;
}
if (k < 1000000 && array[(int)k] != 0)
{
count += array[(int)k] - 1;
break;
}
}
if (array[(int)i] == 0)
array[(int)i] = count;
if (count > max)
max = count;
}
out += max + "\n";
in = ReadLn(20);
}
System.out.print(out);
}
static 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]
thanks everyone
I got AC ,even though with lots of CPU and MEM use.
[cpp]
#include "stdio.h"
int main(void)
{
int i,j,k,max=1,m2=1;
while(scanf("%d %d",&i,&j)==2) {
printf("%d %d ",i,j);
if(i>j){
i ^= j;
j ^= i;
i ^= j;
}
k=j;
while(k>=i)
{
if (k!=1){
j=k;
while (j!=1){
if (j % 2 !=0){
j=(3*j)+1;
}
else{
j/=2;
}
m2++;
}
}
else
{
m2=1;
}
if(m2>max) max=m2;
k--;
m2=1;
}
printf("%d\n",max);
max=1;
}
return 0;
}
[/cpp]
[cpp]
#include "stdio.h"
int main(void)
{
int i,j,k,max=1,m2=1;
while(scanf("%d %d",&i,&j)==2) {
printf("%d %d ",i,j);
if(i>j){
i ^= j;
j ^= i;
i ^= j;
}
k=j;
while(k>=i)
{
if (k!=1){
j=k;
while (j!=1){
if (j % 2 !=0){
j=(3*j)+1;
}
else{
j/=2;
}
m2++;
}
}
else
{
m2=1;
}
if(m2>max) max=m2;
k--;
m2=1;
}
printf("%d\n",max);
max=1;
}
return 0;
}
[/cpp]
-
- New poster
- Posts: 5
- Joined: Wed Sep 29, 2004 7:25 pm
ice_mountain,
It doesn't matter in what format you input/output your code, so long as your output is correct and your program runs in the time limit. Don't think of the judge as a person with a keyboard and monitor, but rather two completely seperate streams (like file input/output), in which the input and output is streamed. When the input is terminated, there will be an EOF.
It doesn't matter in what format you input/output your code, so long as your output is correct and your program runs in the time limit. Don't think of the judge as a person with a keyboard and monitor, but rather two completely seperate streams (like file input/output), in which the input and output is streamed. When the input is terminated, there will be an EOF.
-
- New poster
- Posts: 5
- Joined: Wed Sep 29, 2004 7:25 pm
Please help me
I don't know what I do wrong in this code, the judge replies me a WA, but I've checked almost every thing, when I swap the input numbers I swap them again at the output, the data are in "unsigned long", I've checked some results with other program ... and I still don't know whats wrong, if can see the mistake please tell me 
Thanks!
the code is this one:

Thanks!
the code is this one:
Code: Select all
[c]
#include <stdio.h>
unsigned long a[1000001],A,B;
void ini(){
int i;
for(i=0;i<1000001;i++)
a[i]=0;
}
unsigned long n3p1(unsigned long x){
unsigned long pasos=0;
do{
if (x<1000001)
if(a[x])
return (pasos + a[x]);
if(x%2==0)
x = x /2;
else
x= x*3 +1;
pasos++;
}while(x!=1);
return pasos+1;
}
void swap(){
unsigned long t;
t = A; A= B; B= t;
}
int main(){
unsigned long mayor=0,i,res,s;
int f;
ini();
while ((s=scanf("%ld %ld",&A,&B))!=EOF && s){
mayor = 0;
f = 0;
if (A>B){
swap();
f = 1;
}
for(i=A;i<=B;i++){
res = n3p1(i);
a[i]=res;
if (mayor<res)mayor =res;
}
if (f )
swap();
printf("%ld %ld %ld\n",A,B,mayor);
}
return 0;
}[/c]
I find Out What Was Wrong :D
hehehe, i just find out what was wrong, i just had to initalize
a[1]=1; in the main before all the other stuff,
Anyways I hope the code helps someone else.
a[1]=1; in the main before all the other stuff,

Anyways I hope the code helps someone else.
-
- New poster
- Posts: 1
- Joined: Sun Oct 24, 2004 4:13 pm
100 Time Limit Exceeded [Using JAVA]
I've tried using C++ with the same algorithm,and got AC.
But when using JAVA,always time exceeded:
[java]import java.io.IOException;
import java.util.StringTokenizer;
class Main{
public Main(){
long i=0;
long j=0;
long maxc=0,itemp;
int count=0;
String input;
StringTokenizer idata;
while((input=Main.ReadLn(255))!=null){
idata = new StringTokenizer(input);
i=Long.parseLong(idata.nextToken());
j=Long.parseLong(idata.nextToken());
System.out.print(input);
if(i>j){
long temp=i;
i=j;
j=temp;
}
for (itemp = (i>j/3?(i+1-i%2):(j/3+j%3)); itemp <= j; itemp+=2) {
long n=itemp;
if(n*3+1>j || n/2<i){
while(n!=1){
if(n%2==1){
n=(3*n+1)/2;count+=2;
}
else{
n/=2;count++;
}
}++count;
maxc=maxc<count?count:maxc;
count=0;}
}
for(itemp=(j<2*i?j:2*i);itemp>i;itemp-=2){
long n=itemp;
if(n*3+1>j || n/2<i){
while(n!=1){
if(n%2==1){
n=(3*n+1)/2;count+=2;
}
else{
n/=2;count++;
}
}++count;
maxc=maxc<count?count:maxc;
count=0;}
}
System.out.println(" "+maxc);
}
}
public static void main(String[] args) {
Main t=new Main();
}
static 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]
But when using JAVA,always time exceeded:
Anyone can tell me how to shorten the time??Your program has used more time (10.094 seconds) than the maximum allowed
for this problem by this judge (10 seconds).
[java]import java.io.IOException;
import java.util.StringTokenizer;
class Main{
public Main(){
long i=0;
long j=0;
long maxc=0,itemp;
int count=0;
String input;
StringTokenizer idata;
while((input=Main.ReadLn(255))!=null){
idata = new StringTokenizer(input);
i=Long.parseLong(idata.nextToken());
j=Long.parseLong(idata.nextToken());
System.out.print(input);
if(i>j){
long temp=i;
i=j;
j=temp;
}
for (itemp = (i>j/3?(i+1-i%2):(j/3+j%3)); itemp <= j; itemp+=2) {
long n=itemp;
if(n*3+1>j || n/2<i){
while(n!=1){
if(n%2==1){
n=(3*n+1)/2;count+=2;
}
else{
n/=2;count++;
}
}++count;
maxc=maxc<count?count:maxc;
count=0;}
}
for(itemp=(j<2*i?j:2*i);itemp>i;itemp-=2){
long n=itemp;
if(n*3+1>j || n/2<i){
while(n!=1){
if(n%2==1){
n=(3*n+1)/2;count+=2;
}
else{
n/=2;count++;
}
}++count;
maxc=maxc<count?count:maxc;
count=0;}
}
System.out.println(" "+maxc);
}
}
public static void main(String[] args) {
Main t=new Main();
}
static 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]
your code does not produce the right answer for the sample data.
1. You forget to reset the value of maxc after each run.
2. You skip some numbers (and it happens that one of the number produces the maximum cycle length), eg. 1 10 (your output is 9)
3. for TLE, you might want to consider using memoization so you don't have to recalculate the same thing over-and-over again.
[java]
while((input=Main.ReadLn(255))!=null){
maxc=0; /* add this line */
idata = new StringTokenizer(input);
[/java]
hope this helps
1. You forget to reset the value of maxc after each run.
2. You skip some numbers (and it happens that one of the number produces the maximum cycle length), eg. 1 10 (your output is 9)
3. for TLE, you might want to consider using memoization so you don't have to recalculate the same thing over-and-over again.
[java]
while((input=Main.ReadLn(255))!=null){
maxc=0; /* add this line */
idata = new StringTokenizer(input);
[/java]
hope this helps

100 excuse, somebody could help me. for that wrong answer?
# include <stdio.h>
int n1,n2,n3,n4,n5;
int vec[1000000];
int proceso(long x);
void main()
{int i,j,r,n,con;
for(i=0;i<1000000;i++) vec[i-1]=0;
while(scanf("%d %d",&n1,&n2)==2)
{
n3=n1;n4=n2;
if(n1>n2)
{n5=n1;n1=n2;n2=n5;
}
con=0;
for(i=n1+1;i<=n2;i++)
{if(vec[i-1]!=0) r=vec[i-1];
else
{r=proceso(i);
vec[i-1]=r;
}
if(r>con) con=r;
}
printf("%d %d %d\n",n3,n4,con);
j++;
}
}
int proceso(long x)
{int con;
long c;
float aux;
con=1;
while(x!=1)
{aux=x*1.0/2.0;c=aux;
if(aux!=c) x=x*3+1;
else x/=2;
if((x-1)<1000000.0 && vec[x-1]!=0) return(vec[x-1]+con);
con++;
}
return(con);
}[/b]
int n1,n2,n3,n4,n5;
int vec[1000000];
int proceso(long x);
void main()
{int i,j,r,n,con;
for(i=0;i<1000000;i++) vec[i-1]=0;
while(scanf("%d %d",&n1,&n2)==2)
{
n3=n1;n4=n2;
if(n1>n2)
{n5=n1;n1=n2;n2=n5;
}
con=0;
for(i=n1+1;i<=n2;i++)
{if(vec[i-1]!=0) r=vec[i-1];
else
{r=proceso(i);
vec[i-1]=r;
}
if(r>con) con=r;
}
printf("%d %d %d\n",n3,n4,con);
j++;
}
}
int proceso(long x)
{int con;
long c;
float aux;
con=1;
while(x!=1)
{aux=x*1.0/2.0;c=aux;
if(aux!=c) x=x*3+1;
else x/=2;
if((x-1)<1000000.0 && vec[x-1]!=0) return(vec[x-1]+con);
con++;
}
return(con);
}[/b]
gsfsfws