100 - The 3n + 1 problem

[George]

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 ReadInput(void);
void DoCalculations(void);
void WriteResult(void);

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

void ReadInput(void)
{
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]

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
your output must be:
100 50 result

[George]

[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 ReadInput(void);
void DoCalculations(void);
void WriteResult(void);

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

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

I see your mistake.
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)
   {
      ReadInput();
      DoCalculations();
      WriteResult();
   }
}

become:

Code: Select all

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

I think only this your mistake.
GOOD LUCK

[George]

OK. I solved the problem. The trouble was with the input-output.

[palascari]

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]

[George]

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]

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]

[Hisoka]

I think your problem only at your if(condition) :

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.

I hope this will be help you..........

[Spacey]

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,

[Hisoka]

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]

Thank you for the algorithm explanation !!!


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

Bye for now,

Best wishes,

[25487AH]

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){
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); // 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);
}

//Here load and call calcular
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]

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

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]