371 - Ackermann Functions

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

Moderator: Board moderators

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

371 WA with MANY tests

Post by omega »

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 already_found[MAX_DIS] = {0};
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)
			if (already_found[number]) 
			{
				steps += already_found[number];
				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)
			already_found[seq[a]] = steps - a; 
	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

Post by omega »

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

371 -- WA why?? please help me

Post by OthoMilo »

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;
while((ab=readLine(1000))!=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.");
}
}
}

static String readLine (int max)
{
byte lin [] = new byte [max];
int lg = 0;
int car = -1;
try
{
while (lg < max)
{
car = System.in.read ();
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));
}
}

i don`t know why it`s WA, please some example or advice??

tanvir
New poster
Posts: 22
Joined: Wed Aug 31, 2005 12:09 pm

Post by tanvir »

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?

Post by yanghd »

(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

Post by sds1100 »

i don't know

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

Post by sds1100 »

i don't know

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

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

Post by mukeshtiwari »

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
Location: Bangladesh
Contact:

WHY WA!!! 371

Post by deena sultana »

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. :cry:

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.
thanks 4 reading.

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

WHY WA!!! 371

Post by deena sultana »

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. :cry:

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.
thanks 4 reading.

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

Post by sohel »

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
Location: Bangladesh
Contact:

Post by deena sultana »

i m really a stupid!
Thanks my dear friend.

its AC now :D

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

371..whyWA..

Post by Iffat »

:( :( :( 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?...

Post by Iffat »

:( :( :( 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

Post Reply

Return to “Volume 3 (300-399)”