100 - The 3n + 1 problem

[Per]

cout and scanf works fine together.

In fact, all four of cin, cout, scanf and printf should work fine together (unless you explicitly tell cin/cout to stop synchronising with scanf/printf).

[anupam]

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.

[Elwaryn]

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]

[vladrac]

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]

[vladrac]

Dont bother I got it!

[thincal]

Please just take care this "The integers i and j must appear in the output in the same order in which they appeared in the input "!

[shamim]

I am in the amature stage in Java. So, I just ran your code in my machine. From my observation, it seems that you are taking all the input together and then giving all the output. Well don't do this, take one case of input and give output instantaneously.

[ice_mountain_]

i dont understand the input and output specification... is it that i should print a line everytime a line is entered, or wait till everything is entered then print them all? and how do i know if the input has terminated?

[eleusive]

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.

[ice_mountain_]

ooo. thx, that was enlightening. sry abt the noobness

[chuzpa]

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:

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]

[chuzpa]

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.

[Ray Carter]

I've tried using C++ with the same algorithm,and got AC.
But when using JAVA,always time exceeded:

Your program has used more time (10.094 seconds) than the maximum allowed
for this problem by this judge (10 seconds).

Anyone can tell me how to shorten the time??

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

[wirjawan]

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

[flonav]

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