## 371 - Ackermann Functions

Moderator: Board moderators

omega
New poster
Posts: 5
Joined: Tue Jul 27, 2004 5:37 pm

### 371 WA with MANY tests

I am getting WA on 371. I have looked at several posts and confirmed output with many ACs. I have also checked for all of the general mistakes... 1 -> 3 , and min before max.... Help anyone?

Code: Select all

``````#include <iostream>
#include <vector>
using namespace std;
const int MAX_DIS = 1000000;
int Ackermann_3n(unsigned long long number)
{
vector<unsigned long long> seq;
int steps = 0;
if (number == 1)
{
number = number * 3 + 1;
steps++;
}
while (number != 1)
{
if (number < MAX_DIS)
{
break;
}
seq.push_back(number);
if (number % 2 == 0) number /= 2;
else number = number * 3 + 1;
steps++;
}
for (int a = 0; a < seq.size(); a++)
if (seq[a] < MAX_DIS)
return steps;
}
int main()
{
unsigned long long first, second, lower, upper;
while (cin >> first >> second)
{
if (first == 0 && second == 0) return 0;
lower = first <? second;
upper = first >? second;

unsigned long long max = 0, number = lower, result = 0;
for (unsigned long long a = lower; a <= upper; a++)
{
result = Ackermann_3n(a);
if (result > max)
{
max = result;
number = a;
}
}
cout << "Between " << lower << " and " << upper << ", " << number << " generates the longest sequence of " << max << " values.\n";
}
return 0;
}
``````
inputs that appear to work are ...

Code: Select all

``````  2147483647 2147483647
1 20
35 55
1 1
20 1
1000001  1200000
1000000 1000000
2000000 2000000
4000000 4000000
2147483647 2147483647
16 16
1 2
58 58
19 19
1 3
1 2
2 2
1 2
1 10000
30000 100000
1 1000000
42 18
35 1
20 25
29 9
13 15
6 46
32 28
12 42
46 43
28 37
42 5
3 4
43 33
22 17
19 46
48 27
22 39
20 13
18 50
36 45
0 0
``````
HELP!!!

omega
New poster
Posts: 5
Joined: Tue Jul 27, 2004 5:37 pm
Problem found. I just needed to take a shower and all came to me. One line of code!!!!!!

Note: when storing values for later use, make sure to treat 1 a little differently than everyone else.

OthoMilo
New poster
Posts: 1
Joined: Thu Oct 13, 2005 10:22 pm

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

class Main{
public static void main (String [] args){
Main A=new Main();
A.begin();
}

void begin(){
int a, b, aux;
String ab;
StringTokenizer st = null;
int may=-1,sw=0;
st = new StringTokenizer (ab, " \t \r");
a = (Integer.parseInt (st.nextToken ()));
b = (Integer.parseInt (st.nextToken ()));
if(a==0 && b==0){
break;
}
if(a>b){
aux=a;
a=b;
b=aux;
sw=1;
}
int j=0;
for(int i = a; i <= b; i++){
int cont=0;
double c=i;
while(c!=1 || cont==0){
if(c % 2 == 1){
c = c+(int)(c/2)+1;
cont++;
} else {
c = c/2;
}
cont++;
}
if(cont>may){
j=i;
may=cont;
}
}
if(sw==1){
System.out.println("Between "+b+" and "+a+", "+j+" generates the longest sequence of "+may+" values.");
} else {
System.out.println("Between "+a+" and "+b+", "+j+" generates the longest sequence of "+may+" values.");
}
}
}

{
byte lin [] = new byte [max];
int lg = 0;
int car = -1;
try
{
while (lg < max)
{
if (car == '\n' || car < 0)
{
break;
}
if (car != 13)
{
lin [lg++] += car;
}
}
}
catch (IOException e)
{
return (null);
}
if (lg == 0)
return null;
return (new String (lin, 0, lg));
}
}

tanvir
New poster
Posts: 22
Joined: Wed Aug 31, 2005 12:09 pm
void check();
void special();

int main()
{
data type ackerman;
/* yeh i can give some tips now;
cz i made this tricky problem ac right now:*/
void check();
void special();
return 0;
}

void check()
{
check the followings:

1) for inputs:

1 2
Between 1 and 2, 1 generates the longest sequence of 3 values.
2 1
Between 1 and 2, 1 generates the longest sequence of 3 values.

2) use long long instead of long.

}

void special()
{
/*and this one after u got ac and interested to speedup ur code:*/
pre use ackerman function for all the integer and kept in an array, which is really boring.
}

/*have a nice day*/

yanghd
New poster
Posts: 1
Joined: Mon Feb 20, 2006 7:43 pm

### 371 Ackermann.. Why RE?

(Excuse for my poor English)
Hi, I've posted source code for #371, but 'robot' returns me Runtime Error.
But my code works good at my PC which runs VC++ 6. I'm confused. What's the problem?

Code: Select all

``````#define EMPTY 0
#define LIMIT 10000
#define RATIO 100
#define MAX 20
#include <stdio.h>

typedef unsigned long int ulong;

ulong fAckermann( ulong, ulong [] );
ulong fMaxi( ulong, ulong, ulong [] );

main()
{
ulong i, count;
ulong low[MAX] = { 0 }, upp[MAX] = { 0 };
ulong cycleLength[LIMIT] = { 0 };        /*  caution! Do not use cycleLength[0] */
for(i=1;i<LIMIT/RATIO;i++)
{
cycleLength[i] = fAckermann( i,cycleLength );
}

i = 0, count = 0;
while(i<MAX){

scanf("%d %d",&low[i],&upp[i]);
if(low[i] == 0 && upp[i] == 0) break;
else { count++, i++; }
}

for(i=0;i<count;i++)
{
ulong longest = fMaxi(low[i], upp[i], cycleLength);
printf("Between %d and %d, %d generates the longest sequence of length %d values.\n",low[i],upp[i], longest, cycleLength[longest] );
}

}

ulong fAckermann( ulong x, ulong clist[] )
{
ulong retv = 0;
if(x==1) {
if(clist[1] == EMPTY) retv = 3;
else retv = 0;
}
else{
if(clist[x] == EMPTY){
if(x%2 == 1){
retv = 1+fAckermann(3*x + 1, clist);
}
else{
retv = 1+fAckermann(x/2, clist);
}
}
else retv = clist[x];
}
return retv;
}

ulong fMaxi(ulong l, ulong h, ulong clist[])
{
ulong biggest, i;
biggest = l;
for(i = l + 1;i<=h;i++)
{
if(clist[i] > clist[biggest]) biggest = i;
else ;
}
return biggest;
}
``````

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm
i don't know

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm
i don't know

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
they are supposed to send you a mail telling the error msgs. why dont you see that mail.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### TLE 371

hi everybody i tried to solve prob371 but its giving me TLE.i think it is same as problem100 3n+1 .here is my code .

#include<stdio.h>
#include<string.h>
void swap(long* ,long*);
main()
{
long m,n,i,j,v=0,u;
long temp;
while(scanf("%d%d",&m,&n) && m!=0 || n!=0)
{
if(m>n)
swap(&m,&n);
for(i=m;i<=n;i++)
{
temp=i;
for(j=0;;j++)
{
if(temp%2==0)
{
temp=temp/2;
if(temp==1)
break;
}
else
{
temp=3*temp+1;
if(temp==1)
break;
}
}
if(j>v)
{
v=j;
u=i;
}
}
printf(" Between %d and %d, %d generates the longest sequence of %d values.\n",m,n,u,v+1);
v=0;
}
}

void swap(long *px, long *py)

{
long temp;

temp = *px;
*px = *py;
*py = temp;
}

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Contact:

### WHY WA!!! 371

dear friends.

i dont know why i m getting WA again n again for 371. my i/o seems correct to me. so where is the fault!
i need help. plz help me,plzzzzzzzz.

Code: Select all

``````#include<iostream>
#include<algorithm>
using namespace std;

long long int ackermann(long long int x)
{
long long int len=0;
while(x>1)
{
if(x%2==0)
x=x/2;
else
x=3*x+1;
len++;
}
return len;
}

int main()
{
long long int value,num1,num2,length,clen,u,v;
while(cin>>u>>v)
{
if(u==0 && v==0)
break;
if(u>v)
{
num1=v;
num2=u;}
else
{
num1=u;
num2=v;}
length=ackermann(num1);
value=num1;
for(long long int i=num1+1;i<=num2;i++)
{
clen=ackermann(i);
if(clen>length)
{
length=clen;
value=i;
}
}
cout<<"Between "<<num1<<" and "<<num2<<", "<<value<<" generates the longest sequence of "<<length<<" values."<<endl;

}
return 0;

}
``````

INPUTS:
42 18
35 1
20 25
29 9
13 15
6 46
32 28
12 42
46 43
28 37
42 5
3 4
43 33
22 17
19 46
48 27
22 39
20 13
18 50
36 45
0 0
OUTPUTS:
Between 18 and 42, 27 generates the longest sequence of 111 values.
Between 1 and 35, 27 generates the longest sequence of 111 values.
Between 20 and 25, 25 generates the longest sequence of 23 values.
Between 9 and 29, 27 generates the longest sequence of 111 values.
Between 13 and 15, 14 generates the longest sequence of 17 values.
Between 6 and 46, 27 generates the longest sequence of 111 values.
Between 28 and 32, 31 generates the longest sequence of 106 values.
Between 12 and 42, 27 generates the longest sequence of 111 values.
Between 43 and 46, 43 generates the longest sequence of 29 values.
Between 28 and 37, 31 generates the longest sequence of 106 values.
Between 5 and 42, 27 generates the longest sequence of 111 values.
Between 3 and 4, 3 generates the longest sequence of 7 values.
Between 33 and 43, 41 generates the longest sequence of 109 values.
Between 17 and 22, 18 generates the longest sequence of 20 values.
Between 19 and 46, 27 generates the longest sequence of 111 values.
Between 27 and 48, 27 generates the longest sequence of 111 values.
Between 22 and 39, 27 generates the longest sequence of 111 values.
Between 13 and 20, 18 generates the longest sequence of 20 values.
Between 18 and 50, 27 generates the longest sequence of 111 values.
Between 36 and 45, 41 generates the longest sequence of 109 values.

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Contact:

### WHY WA!!! 371

dear friends.

i dont know why i m getting WA again n again for 371. my i/o seems correct to me. so where is the fault!
i need help. plz help me,plzzzzzzzz.

Code: Select all

``````#include<iostream>
#include<algorithm>
using namespace std;

long long int ackermann(long long int x)
{
long long int len=0;
while(x>1)
{
if(x%2==0)
x=x/2;
else
x=3*x+1;
len++;
}
return len;
}

int main()
{
long long int value,num1,num2,length,clen,u,v;
while(cin>>u>>v)
{
if(u==0 && v==0)
break;
if(u>v)
{
num1=v;
num2=u;}
else
{
num1=u;
num2=v;}
length=ackermann(num1);
value=num1;
for(long long int i=num1+1;i<=num2;i++)
{
clen=ackermann(i);
if(clen>length)
{
length=clen;
value=i;
}
}
cout<<"Between "<<num1<<" and "<<num2<<", "<<value<<" generates the longest sequence of "<<length<<" values."<<endl;

}
return 0;

}
``````

INPUTS:
42 18
35 1
20 25
29 9
13 15
6 46
32 28
12 42
46 43
28 37
42 5
3 4
43 33
22 17
19 46
48 27
22 39
20 13
18 50
36 45
0 0
OUTPUTS:
Between 18 and 42, 27 generates the longest sequence of 111 values.
Between 1 and 35, 27 generates the longest sequence of 111 values.
Between 20 and 25, 25 generates the longest sequence of 23 values.
Between 9 and 29, 27 generates the longest sequence of 111 values.
Between 13 and 15, 14 generates the longest sequence of 17 values.
Between 6 and 46, 27 generates the longest sequence of 111 values.
Between 28 and 32, 31 generates the longest sequence of 106 values.
Between 12 and 42, 27 generates the longest sequence of 111 values.
Between 43 and 46, 43 generates the longest sequence of 29 values.
Between 28 and 37, 31 generates the longest sequence of 106 values.
Between 5 and 42, 27 generates the longest sequence of 111 values.
Between 3 and 4, 3 generates the longest sequence of 7 values.
Between 33 and 43, 41 generates the longest sequence of 109 values.
Between 17 and 22, 18 generates the longest sequence of 20 values.
Between 19 and 46, 27 generates the longest sequence of 111 values.
Between 27 and 48, 27 generates the longest sequence of 111 values.
Between 22 and 39, 27 generates the longest sequence of 111 values.
Between 13 and 20, 18 generates the longest sequence of 20 values.
Between 18 and 50, 27 generates the longest sequence of 111 values.
Between 36 and 45, 41 generates the longest sequence of 109 values.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
deena-

1 generates a sequence of lenght 3, but your code outputs 0.
Hope you can find the error.

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Contact:
i m really a stupid!
Thanks my dear friend.

its AC now

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

### 371..whyWA..

I got WA for following code...plzzz help me to find the error

Code: Select all

``````#include<stdio.h>

int main()
{

unsigned long  i,j,n,t,p,temp,count,max,n1;

while(scanf("%lu %lu",&i,&j)==2)
{
max=0;
p=0;
if(i==0 && j==0){break;}
if(i>j)
{
temp=i;
i=j;
j=temp;
printf("Between %lu and %lu, ",j,i);
}

else
{
printf("Between %lu and %lu, ",i,j);
}

n=i;
while(n<=j)

{

count=0;
if(n==1)
{
n1=3*n+1;
count++;

t=n1;
while(t>1)
{

if(t%2==0)

{t=t/2;}

else

{t=3*t+1;}
count++;
}

if(max<count)
{
max=count;
p=n;
}
}
else
{
t=n;
while(t>1)
{

if(t%2==0)

{t=t/2;}

else

{
t=3*t+1;}

count++;
}

if(max<count)
{
max=count;
p=n;
}
}

n=n+1;

}

printf("%lu generates the longest sequence of %lu values.\n",p,max);
}

return 0;
}

``````
thanx

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

### 371..why WA?...

I got WA for following code...plzzz help me to find the error

Code: Select all

``````#include<stdio.h>

int main()
{

unsigned long  i,j,n,t,p,temp,count,max,n1;

while(scanf("%lu %lu",&i,&j)==2)
{
max=0;
p=0;
if(i==0 && j==0){break;}
if(i>j)
{
temp=i;
i=j;
j=temp;
printf("Between %lu and %lu, ",j,i);
}

else
{
printf("Between %lu and %lu, ",i,j);
}

n=i;
while(n<=j)

{

count=0;
if(n==1)
{
n1=3*n+1;
count++;

t=n1;
while(t>1)
{

if(t%2==0)

{t=t/2;}

else

{t=3*t+1;}
count++;
}

if(max<count)
{
max=count;
p=n;
}
}
else
{
t=n;
while(t>1)
{

if(t%2==0)

{t=t/2;}

else

{
t=3*t+1;}

count++;
}

if(max<count)
{
max=count;
p=n;
}
}

n=n+1;

}

printf("%lu generates the longest sequence of %lu values.\n",p,max);
}

return 0;
}

``````
thnx