100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Sep 22, 2004 12:02 am

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:

Post by anupam » Wed Sep 22, 2004 12:14 am

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":wink: ). 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

Post by Elwaryn » Wed Sep 22, 2004 5:07 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[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
New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

thanks everyone

Post by vladrac » Wed Sep 22, 2004 5:51 pm

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
New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

I got it

Post by vladrac » Wed Sep 22, 2004 5:53 pm

Dont bother I got it!

thincal
New poster
Posts: 7
Joined: Thu Sep 23, 2004 7:45 am

Post by thincal » Sat Sep 25, 2004 12:39 pm

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 "!

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Sep 28, 2004 2:27 pm

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

Post by ice_mountain_ » Wed Sep 29, 2004 9:52 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

Post by eleusive » Wed Sep 29, 2004 11:40 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.

ice_mountain_
New poster
Posts: 5
Joined: Wed Sep 29, 2004 7:25 pm

Post by ice_mountain_ » Fri Oct 01, 2004 2:40 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:

Please help me

Post by chuzpa » Fri Oct 08, 2004 8:03 am

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

I find Out What Was Wrong :D

Post by chuzpa » Fri Oct 08, 2004 8:47 am

hehehe, i just find out what was wrong, i just had to initalize
a[1]=1; in the main before all the other stuff, :D
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]

Post by Ray Carter » Mon Oct 25, 2004 9:14 am

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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by wirjawan » Mon Oct 25, 2004 9:52 pm

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
New poster
Posts: 2
Joined: Mon Oct 25, 2004 7:01 am
Location: mexico

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

Post by flonav » Fri Nov 19, 2004 7:11 am

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

Post Reply

Return to “Volume 1 (100-199)”