## 100 - The 3n + 1 problem

Moderator: Board moderators

George
New poster
Posts: 8
Joined: Tue Mar 11, 2003 10:29 pm
Can you help me?

What's wrong with the following code. It returns wrong answer.

[cpp]#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

int i, j, c, r, scan_r;

int CalculateCycleLength(int n);

void DoCalculations(void);
void WriteResult(void);

void main(void)
{
scan_r = 2;
while (scan_r == 2)
{
DoCalculations();
WriteResult();
}
}

{
scan_r = scanf ("%d %d", &i, &j);
if (i > j)
{
int t = j;
j = i;
i = t;
}
}

void DoCalculations(void)
{
int t;
r = 0;
for (c = i; c <= j; c++)
{
t = CalculateCycleLength(c);
if (t > r)
r = t;
}
}

void WriteResult(void)
{
printf ("%d %d %d\n", i, j, r);
}

int CalculateCycleLength(int n)
{
int cl = 1;
while (n != 1)
{
if (n % 2 == 1)
n = 3 * n + 1;
else
n = n / 2;
cl++;
}
return cl;
}[/cpp][/cpp]
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
try to change your data type from int to long or unsigned long. And you can't swap A to B when A > B.
like that :
100 50
100 50 result
George
New poster
Posts: 8
Joined: Tue Mar 11, 2003 10:29 pm
[cpp]#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

long i, j, c, r, scan_r;
bool sw;

long CalculateCycleLength(long n);

void DoCalculations(void);
void WriteResult(void);

void main(void)
{
scan_r = 2;
while (scan_r == 2)
{
DoCalculations();
WriteResult();
}
}

{
scan_r = scanf ("%d %d", &i, &j);
if (i > j)
{
long t = j;
j = i;
i = t;
sw = true;
}
else
sw = false;
}

void DoCalculations(void)
{
long t;
r = 0;
for (c = i; c <= j; c++)
{
t = CalculateCycleLength(c);
if (t > r)
r = t;
}
}

void WriteResult(void)
{
if (sw)
printf ("%d %d %d\n", j, i, r);
else
printf ("%d %d %d\n", i, j, r);
}

long CalculateCycleLength(long n)
{
long cl = 1;
while (n != 1)
{
if (n % 2 == 1)
n = 3 * n + 1;
else
n = n / 2;
cl++;
}
return cl;
}[/cpp]

What's wrong here?
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
first:

Code: Select all

``````void ReadInput(void)
{
scan_r = scanf  ("%d %d", &i, &j);
if (i > j)
{
long t = j;
j = i;
i = t;
sw = true;
}
else
sw = false;
}

void WriteResult(void)
{
if (sw)
printf ("%d %d %d\n", j, i, r);
else
printf ("%d %d %d\n", i, j, r);
}
``````
for long int you don't write %d, change %d with %ld.

and

Code: Select all

``````void main(void)
{
scan_r = 2;
while (scan_r == 2)
{
DoCalculations();
WriteResult();
}
}
``````
become:

Code: Select all

``````void main(void)
{
scan_r = 2;
while (scan_r == 2)
{
DoCalculations();
WriteResult();
}
}``````
I think only this your mistake.
GOOD LUCK
George
New poster
Posts: 8
Joined: Tue Mar 11, 2003 10:29 pm
OK. I solved the problem. The trouble was with the input-output.
palascari
New poster
Posts: 1
Joined: Sat Mar 15, 2003 6:55 pm

### 100 can someone tell me why?

I write this program and i receive this WA:
Your program has not solved the problem. It ran during 3.785 seconds.
Why?

#include <iostream.h>
int main()
{
long min,max,i,min1,t,len,lenm;
lenm=1;
while(cin >> min >> max)
{
lenm=1;
min1=min;
for(i = min; i <= max; i++)
{
len=0;
min=i;
while((min!=1) & (i!=1))
{
len=len++;
t = min%2;
if (t==0) min =min/2;
else min=3*min+1;
}
if (lenm==1) lenm=len+1;
if (lenm<=len+1) lenm=len+1;
}
cout <<min1 <<" " << max
<<" " <<lenm <<" ";
}
return 0;
}

THANKS[/cpp]
Palascari Cosmin
George
New poster
Posts: 8
Joined: Tue Mar 11, 2003 10:29 pm
You should consider when min>max.

[cpp]len=len++; [/cpp]
this is not a very good line of code. The following is better:
[cpp]len++;[/cpp]
OR
[cpp]len=len+1;[/cpp]
Spacey
New poster
Posts: 3
Joined: Thu Mar 20, 2003 5:41 pm
Contact:

### problem 100 - Wrong Answer (WA)

HI, if someone could spend 2 mins. looking at my code and figure out why the judge gives me (WA)... and spent 3.486 seconds with it... Altough I've tried with the example on the problem page and gives me the correct answer... I've tried also with numbers like (1 2000) and (200 5000)... I care about the input order and cases like (2 2), (20 20)... Dunno what's wrong...

TIA.

[c]
#include <stdio.h>
#include <stdlib.h>

/* @JUDGE_ID: ******* 100 C "Using an array..." */
int maxCycleLength(int i1, int i2);

int main() {
int a,b;

while (scanf("%d %d",&a, &b)==2) {
if(a>0 && a<1000001 && b>0 && b<1000001)
{
printf("%d %d %d\n",a,b,maxCycleLength(a,b));
}
}
return 0;
}

int maxCycleLength(int i1, int i2) {
int mcc_Counter=1, max=1, temp=0;
int j=0,j2;

/* If they're equal...*/
if(i1==1 && i2==1) return 1;

/* Swap them if necessary*/
if(i2<i1){temp=i2;i2=i1;i1=temp;}
j2=i2;

/* While i2 haven't reached i1 continue to compute each cycleLength */
while(j2>=i1) {
if (max<=mcc_Counter) max=mcc_Counter;
mcc_Counter=1;
j=j2;
if(j==1) mcc_Counter++;
while(j>1) {
if (j%2!=0) {j=3*j+1;mcc_Counter++;}
else {j=j/2;mcc_Counter++;}
}
j2--;
}
return max;
}
[/c]
:::: Spacey
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Code: Select all

``````  while(j2>=i1) {
if (max<=mcc_Counter) max=mcc_Counter;
mcc_Counter=1;
j=j2;
if(j==1) mcc_Counter++;
while(j>1) {
if (j%2!=0) {j=3*j+1;mcc_Counter++;}
else {j=j/2;mcc_Counter++;}
}
j2--;
}
``````
if you declarate like this you can get wrong answer if the max is the last mcc_Counter.
If you want a sample input when you get WA try this :

Code: Select all

``3 4``
you can check the output with manual.

Spacey
New poster
Posts: 3
Joined: Thu Mar 20, 2003 5:41 pm
Contact:

### Thank you for your help !!!

I've tried to change the line you mentioned, altough I was not able to figure out what was wrong... So I decided to write a new program in which I use two functions :

[c]
/* To compute the cycleLength of n1. */
int cycle(int n1);

/* Computes the maximum cycleLength between n1 and n2 */
int mCycleLength(int n1, int n2);
[/c]

So, my program was Accepted.

Just one last thing :

The program took 4.55 seconds to achieve the results, altough I've seen submited programs solving the problem in less than 1 sec. !!!

Is this because I use two functions ?
I'm careful in not to create variables that won't be needed...

So, can you point me what does really matter when we want a fast program ??

Thank you my friend.
Best Regards,
:::: Spacey
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
In my previous post mean you only change from :

Code: Select all

``````while(j2>=i1) {
if (max<=mcc_Counter) max=mcc_Counter; =>THIS IS YOUR MISTAKE
mcc_Counter=1;
j=j2;
if(j==1) mcc_Counter++;
while(j>1) {
if (j%2!=0) {j=3*j+1;mcc_Counter++;}
else {j=j/2;mcc_Counter++;}
}
j2--;
}
``````
this is a simulation from your program when the input is 3 4.
first : max=mcc_Counter=1; after that you seek the mcc_Counter from 4.
second : max=mcc_Counter from 4; after that you seek the mcc_Counter from 3.

after that you out from while because j2<i1.
I mean before you just change to

Code: Select all

``````while(j2>=i1) {

mcc_Counter=1;
j=j2;
if(j==1) mcc_Counter++;
while(j>1) {
if (j%2!=0) {j=3*j+1;mcc_Counter++;}
else {j=j/2;mcc_Counter++;}
}
j2--;
if (max<=mcc_Counter) max=mcc_Counter;
}

``````
if you ask why we can get less then 1 s. there are a algorithm to increase speed.
this is that algo:
1. you compute all cycle lenght from 1 to 1000000 and store them into array.
2. to compute that you can begin from 1 and end at 1000000. and where the number == the previous number you no necessary to compute that number again.
(I'm sorry for my bad english).
This a example from that simulation.
for number 16 cycle is: 16 8 4 2 1 the cycle lenght is 5.
for number 32 cycle is : 32 16 8 4 2 1 the cycle lenght is 6.
from this we can see for number 32 when the cycle is 16, we just add the cycle lenght when that number not 16 with cycle lenght from 16.

this is can make the program run faster.
Spacey
New poster
Posts: 3
Joined: Thu Mar 20, 2003 5:41 pm
Contact:
Thank you for the algorithm explanation !!!

I haven't implemented i yet but i'll do it ASAP.

Bye for now,

Best wishes,
:::: Spacey
25487AH
New poster
Posts: 2
Joined: Fri Apr 11, 2003 4:58 pm
Location: Venezuela
Contact:

### WA whit 100 in JAVA, but i dont know why

Hi.
i thing my code works fine but i still have a wa. I have some tab cases to improve time.

(when the input is: 1 1000000 the output is: 525)

thats my code, can some one tell me whats wrong please?:
[java]
/* @BEGIN_OF_SOURCE_CODE */
// @JUDGE_ID: 25487AH 100 Java

import java.io.*;
import java.util.StringTokenizer;

class Main{

static String ReadLn (int maxLg){ // utility function to read from stdin
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

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); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point

}

public String calcular(int[] l){
String res="";
int cont=0,max=0;
long j;
int superior=l[1];
if(superior%2==0)
superior++;
int cotInf=l[0];

//tabs values
if((l[0]<=837799)&&(l[1]>=837799))
return Integer.toString(l[0])+" "+Integer.toString(l[1])+" 525";
else if((l[0]<=626331)&&(l[1]>=626331))
return Integer.toString(l[0])+" "+Integer.toString(l[1])+" 509";
else if((l[0]<=939497)&&(l[1]>=939497))
return Integer.toString(l[0])+" "+Integer.toString(l[1])+" 507";
else if((l[0]<=704623)&&(l[1]>=704623))
return Integer.toString(l[0])+" "+Integer.toString(l[1])+" 504";
else if((l[0]<=910107)&&(l[1]>=910107))
return Integer.toString(l[0])+" "+Integer.toString(l[1])+" 476";
else if((l[0]<=511935)&&(l[1]>=511935))
return Integer.toString(l[0])+" "+Integer.toString(l[1])+" 470";
else if((l[0]<410000)&&(l[1]>511935))
cotInf=410000;

//tabs values
if(cotInf%2==0){
cont=1;
j=cotInf;
while(j!=1){
if(j==575){
cont+=30;
break;
}
if(j%2==0)
j=j/2;
else
j=(3*j)+1;
cont++;
}
if(max<cont){
//System.gc();
max=cont;
}
cotInf++;
}

//REAL CODE
for (int i=cotInf; i<=l[1]; i+=2){
cont=1;
j=i;
while(j!=1){
if(j==575){//tabs
cont+=30;
break;
}
if(j%2==0)
j=j/2;
else
j=(3*j)+1;
cont++;
}
if(max<cont){
//System.gc();
max=cont;
}

}

return Integer.toString(l[0])+" "+Integer.toString(l[1])+" "+Integer.toString(max);
}

void Begin(){
String input;
StringTokenizer idata;
int res[];
while ((input = Main.ReadLn (255)) != null){
res=new int[9];
idata = new StringTokenizer(input);
res[0]=Integer.parseInt((idata.nextToken()).trim());
res[1]=Integer.parseInt((idata.nextToken()).trim());
System.out.println(calcular(res));
}

}

}
/* @END_OF_SOURCE_CODE */

/* @END_OF_SOURCE_CODE */[/java]
thebear
New poster
Posts: 2
Joined: Sat Apr 19, 2003 8:53 am

### Plz help 100.It's always WA

[cpp]
This first time I do acm
I can run follow code in my pc
but acm always tell me WA
Plz anyone tell me how to fix it.
-------------------------------------------------------------------
#include <iostream.h>
#include <iomanip.h>

int main ()
{
int a=0;
float i,i1,j,j1,c,b,k,c3;
double c1, c2;
k = 0;
b = 0;

for(;;)
{
cout << "Please input the number i ,j to define the range of n:";
cout << "\nThe i:";
cin >> i;
i1 = int(i);
cout << "\nThe j:";
cin >> j;
j1 = int(j);
if(i*j <= 0 || i > 1000000 || j > 1000000)
cout << "i j must more than 0 and less than 1000000.\nPlease retry.";
if(i != i1 || j != j1)
cout << "i j must whole number.\nPlease retry.";
if(i == i1 && j == j1 && i > 0 && j > 0 && i <= 1000000 && j <= 1000000 )
break;
}
if(i<=j)
{
while( i+k <= j)
{
a=1;
c3 = i + k ;

for(;;)
{
c1 = c3/2;
c2 = int(c3/2);
if( c1 == c2)
c3 = (c3)/2;
if( c1 != c2)
c3 = 3*(c3) + 1;
a++;
if(c3 ==1)
break;
}
if(a >= b)
b = a;
k++;
}
}
if(i>=j)
{
while( j+k <= i)
{
a=1;
c3 = j + k ;

for(;;)
{
c1 = c3/2;
c2 = int(c3/2);
if( c1 == c2)
c3 = (c3)/2;
if( c1 != c2)
c3 = 3*(c3) + 1;
a++;
if(c3 ==1)
break;
}
if(a >= b)
b = a;
k++;
}
}
cout << "The Max cycle between " << i <<" to " << j << " is " << b << endl;

return 0;
}[/cpp]
thebear
New poster
Posts: 2
Joined: Sat Apr 19, 2003 8:53 am
fix
[cpp]
#include <iostream.h>
#include <iomanip.h>

int main ()
{
int a=0;
float i,i1,j,j1,c,b,k,c3;
double c1, c2;
k = 0;
b = 0;

for(;;)
{
cout << "Please input the number i ,j to define the range of n:";
cout << "\nThe i:";
cin >> i;
i1 = int(i);
cout << "\nThe j:";
cin >> j;
j1 = int(j);
if(i*j <= 0 || i > 1000000 || j > 1000000)
cout << "i j must more than 0 and less than 1000000.\nPlease retry.";
if(i != i1 || j != j1)
cout << "i j must whole number.\nPlease retry.";
if(i == i1 && j == j1 && i > 0 && j > 0 && i <= 1000000 && j <= 1000000 )
break;
}
if(i<=j)
{
while( i+k <= j)
{
a=1;
c3 = i + k ;

for(;;)
{
c1 = c3/2;
c2 = int(c3/2);
if( c1 == c2)
c3 = (c3)/2;
if( c1 != c2)
c3 = 3*(c3) + 1;
a++;
if(c3 ==1)
break;
}
if(a >= b)
b = a;
k++;
}
}
if(i>=j)
{
while( j+k <= i)
{
a=1;
c3 = j + k ;

for(;;)
{
c1 = c3/2;
c2 = int(c3/2);
if( c1 == c2)
c3 = (c3)/2;
if( c1 != c2)
c3 = 3*(c3) + 1;
a++;
if(c3 ==1)
break;
}
if(a >= b)
b = a;
k++;
}
}
cout << "The Max cycle between " << i <<" to " << j << " is " << b << endl;

return 0;
}[/cpp]