## 100 - The 3n + 1 problem

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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"

Elwaryn
New poster
Posts: 1
Joined: Wed Sep 22, 2004 5:01 am
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;

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";
}
System.out.print(out);
}

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

try
{
while (lg < maxLg)
{
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]

New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

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

New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

### I got it

Dont bother I got it!

thincal
New poster
Posts: 7
Joined: Thu Sep 23, 2004 7:45 am
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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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_
New poster
Posts: 5
Joined: Wed Sep 29, 2004 7:25 pm
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
New poster
Posts: 9
Joined: Tue Sep 28, 2004 6:57 am
Location: United States
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_
New poster
Posts: 5
Joined: Wed Sep 29, 2004 7:25 pm
ooo. thx, that was enlightening. sry abt the noobness

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

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,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
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### I find Out What Was Wrong :D

hehehe, i just find out what was wrong, i just had to initalize
a=1; in the main before all the other stuff, Anyways I hope the code helps someone else.

Ray Carter
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:
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;
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();

}

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

try
{
while (lg < maxLg)
{
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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
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]
maxc=0; /* add this line */
idata = new StringTokenizer(input);
[/java]

hope this helps flonav
New poster
Posts: 2
Joined: Mon Oct 25, 2004 7:01 am
Location: mexico

### 100 excuse, somebody could help me. for that wrong answer?

# include <stdio.h>
int n1,n2,n3,n4,n5;
int vec;
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