371 - Ackermann Functions
Moderator: Board moderators
-
- New poster
- Posts: 44
- Joined: Tue Jun 06, 2006 6:44 pm
- Location: Nova Scotia, Canada
- Contact:
I've tried a lot of inputs without no incorrect outputs.
Can somebody give me some critical inputs or correct my code?
I appreciate that.

Can somebody give me some critical inputs or correct my code?
I appreciate that.
Code: Select all
Code removed after AC.
Missed the lines:
L = the lower boundary value in the sequence
H = the upper boundary value in the sequence
Thanks for Rio's help!!

Last edited by gba356 on Mon Jun 18, 2007 1:42 pm, edited 1 time in total.
Re: check this input & output
From previous post.osan wrote:Dear Aengus
Check these1 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.
----
Rio
-
- New poster
- Posts: 4
- Joined: Sun Sep 09, 2007 1:42 pm
- Location: Indonesia
- Contact:
try some cases from Aengus
i try your cases from Aengus..
i try input --> 1 10000
but that inputs changed in my code...
please some body check my code...
sorry my english bad..
thx before..
Code: Select all
1 2
1 10000
30000 100000
1 1000000
2000000000 2001000000
1234567890 1235678901
0 0
i try input --> 1 10000
but that inputs changed in my code...
please some body check my code...
Code: Select all
#include<stdio.h>
#include<stdlib.h>
int main()
{
long long input[1000][2],temp;
long long data[1000][2];
long long i=-1,j,k,l,cad,bny,index;
do
{
i++;
//test 1 case input--> 1 10000
scanf("%I64d %I64d",&input[i][0],&input[i][1]);
if(input[i][0]>input[i][1])
{
temp = input[i][0];
input[i][0] = input[i][1];
input[i][1] = temp;
}
}while(input[i][0] != 0 && input[j][1] != 0);
for(j=0 ;j<i ;j++)
{
index=0;
for(l=0,k=input[j][0] ;k<=input[j][1] ;k++,l++)
{
cad = k;
bny=0;
do
{
if( cad%2 == 0 )
cad/=2;
else
cad = (3*cad)+1;
bny++;
if(cad==1)
break;
}while(1);
if(l!=0 && bny>data[index][0])
{
index = l;
}
data[l][0] = bny;
data[l][1] = k;
}
//why change ?? --> input[0][0] = 1 , input[0][1] = 10000
printf("Between %I64d and %I64d, %I64d generates the longest sequence of %I64d values.\n",input[j][0],input[j][1],data[index][1],data[index][0]);
}
system("pause");
return 0;
}
thx before..
sorry my english is bad
-
- New poster
- Posts: 6
- Joined: Sat Sep 29, 2007 11:11 am
how about .160s
I got .160s~~ however I didn't pay much attention to the efficiency of algorithm when I'm writing the code~~~it's just lucky
Last edited by mistycheney on Fri Oct 12, 2007 7:25 am, edited 1 time in total.
TLE 371.....plzzzzzzz Help
I got Accc. in 100 by this code. But what's up hear.. plzzzzzzz help me....

Code: Select all
#include<stdio.h>
int main()
{
long long n,r,i,p,s,count,max,num;
while(scanf("%lld %lld",&n,&p)==2)
{
if(n==0&&p==0)
{
break;
}
else
{
printf("Between %lld and %lld, ",n,p);
if(n>p)
{
long long int t;
t = n;
n = p;
p = t;
}
max=0;
for(i=n;i<=p;i++)
{
count=0;
s = i;
while(s!=1)
{
count = count + 1;
r=s%2;
if(r==1)
s=3*s+1;
else
s=s/2;
}
if(count>max)
{
max=count;
num=i;
}
}
printf("%lld generates the longest sequence of %lld values\n",num,max);
}
}
return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
no..... this shouldn't be....
Over come previous problem... now time limit on .652 it ok, but giving wrong answer.... plzzzzzzzzzz help me
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
no..... this shouldn't be....
Over come previous problem... now time limit on .652 it ok, but giving wrong answer.... plzzzzzzzzzz help me
Code: Select all
#include<stdio.h>
int main()
{
long long int a,n,b,count,max,i,t,num,x[1000];
while(scanf("%lld %lld",&a,&b)==2)
{
if(a==0&&b==0)
{
break;
}
else
{
printf("Between %lld and %lld, ",a,b);
if(a>b)
{
t=b;
b=a;
}
else
t=a;
max=0;
for(i=t;i<=b;i++)
{
count=0;
n=i;
while(n!=1)
{
if(n%2==1)
n=3*n+1;
else
n=n/2;
count++;
}
if(count>=max)
{
num=i;
max=count;
}
}
printf("%lld generates the longest sequence of %lld values.\n",num,max);
}
}
return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
371 - Ackermann Functions #TLE. Please Help!
Please help me. I found the TLE. Please help me to solve the problem.
Code: Select all
#include<stdio.h>
int main()
{
long l,h,j,i,s,count,max,t;
while(scanf("%ld %ld",&l,&h)==2)
{
max = 0;
if(l==0&&h==0) break;
if(l>h)
{
t = h;
h = l;
l = t;
}
for(j = l; j<=h; j++)
{
i = j;
count = 0;
while(i!=1)
{
if(i%2==0)
i = i/2;
else
i = i*3+1;
count++;
if(count>max)
{
max = count;
s = j;
}
//if(i==1) break;
}
}
printf("Between %ld and %ld, %ld generates the longest sequence of %ld values.\n",l,h,s,max);
}
return 0;
}
Mahedee
371 WA
I dont know the wrong of the code
I count 1 to 10000 first
if the input < 10000, I just use the len[input]
please tell me what is wrong
thank you very much
I count 1 to 10000 first
if the input < 10000, I just use the len[input]
please tell me what is wrong
thank you very much
Code: Select all
#include<stdio.h>
#define MAX 10000
struct num
{
unsigned int length;
unsigned int value;
};
int len[MAX];
int ackermann(unsigned int n)
{
unsigned int i,length=0;
for(i=n,length=0; i!=1;length++)
{
if(i < MAX)
return len[i];
if(i%2 == 0)
i = i/2;
else
i = 3*i+1;
}
return length;
}
void init()
{
for(int i=0; i<MAX; i++)
len[i] = 0;
len[1] = 0;
len[2] = 1;
for(int i=3; i<MAX; i++)
{
int length=0;
for(int j=i; j!=1; length++ )
{
if(j<MAX)
{
if(len[j] != 0)
{
len[i] = len[j] + length;
break;
}
}
if(j%2 == 0)
j = j/2;
else
j = 3*j+1;
}
if(len[i] == 0)
len[i] = length;
}
}
int main()
{
unsigned int L,H,tmp;
unsigned int length;
struct num max;
scanf("%u %u",&L,&H);
init();
while(!(L==0 &&H==0))
{
if(L>H)
{
tmp = L;
L = H;
H = tmp;
}
max.length = 0;
for(unsigned int i=L; i<=H; i++)
{
if(i%2 == 0)
length = ackermann(i/2)+1;
else
length = ackermann(3*i+1)+1;
if(length > max.length)
{
max.length = length;
max.value = i;
}
}
printf("Between %u and %u, %u generates the longest sequence of %u values.\n",L,H,max.value,max.length);
scanf("%u %u",&L,&H);
}
return 0;
}
-
- New poster
- Posts: 13
- Joined: Mon Sep 08, 2008 6:57 pm
- Location: State University of Bangladesh
Re: 371 - Ackermann Functions #TLE. Please Help!
try to do some memoization.
Don't calculate for the same input again, just save the cycle length in an array...
Don't calculate for the same input again, just save the cycle length in an array...
Never think too hard, let ideas come to you...