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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 371 - Anckerman Functions - Why WA ?

Post by brianfry713 »

remove the saver and you will get AC.
Check input and AC output for thousands of problems on uDebug!

kia.masster
New poster
Posts: 6
Joined: Thu Dec 22, 2011 8:47 am

Re: 371 - Anckerman Functions

Post by kia.masster »

Thank you Brian...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 371 - Ackermann Functions... Why WA????

Post by brianfry713 »

Input:

Code: Select all

1 2
0 0
AC output:

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.
Check input and AC output for thousands of problems on uDebug!

jocker1
New poster
Posts: 5
Joined: Sat May 19, 2012 11:10 pm

Re: 371 - Ackermann Functions... Why WA????

Post by jocker1 »

Yeah you were right brian, i forgot that case completely....
Thanks a lot brianfry problem AC.......

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

Re: 371 - Ackermann Functions... Why WA????

Post by vpanait »

i consider the problem statement a bit confusing, I got AC only after I've taken care that the input pair is ordered [L H]. Ex:
1 2
2 1
mean the same thing, and both are valid input.

enjoy

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

Re: 371 - Ackermann Functions... Why WA????

Post by gr81 »

did some one test this test case
3 2147483647

how long it will take.....

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

Re: 371 - Ackermann Functions... Why WA????

Post by gr81 »

I am getting TLE...in above test case.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 371 - Ackermann Functions... Why WA????

Post by brianfry713 »

That input is not valid. The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long.
Check input and AC output for thousands of problems on uDebug!

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

Re: 371 - Ackermann Functions... Why WA????

Post by gr81 »

thanks for clarification, but issue was something else...got AC.

atiburrahman09
New poster
Posts: 6
Joined: Mon Mar 26, 2012 10:12 pm

Re: 371 - Ackermann Functions... Why WA????

Post by atiburrahman09 »

hello friend i tried to handle the case 1 2.but when i input the file output never comes.can anyone help me.

here is my code...

#include<iostream>
using namespace std;
int main()
{
long long int x, y,i,count,max=0,v,n=0,temp;
while(cin>>x>>y)
{
max=0;
if(x==0 && y==0)
break;
if(y<x)
{
temp=x;
x=y;
y=temp;
}

for(i=x; i<=y; i++)
{

count=0;
while(n!=1)
{
n=i;
if(n%2==0)
{
n=n/2;
count++;
}
else
{
n=(3*n+1);
count++;
}

if(max < count)
{
max=count;

v = i;
}
}
}
cout<<"Between "<<x<<" and " <<y <<", "<< v <<" generates the longest sequence of "<<max<<" values."<<endl;
}


return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 371 - Ackermann Functions... Why WA????

Post by brianfry713 »

Try changing lines 22-24 from:

Code: Select all

while(n!=1)
{
n=i;
to:

Code: Select all

n=i;
while(n!=1)
{
Check input and AC output for thousands of problems on uDebug!

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 371 - Ackermann Functions... Why WA????

Post by alimbubt »

The only tricky test case for this problem is
Input:

Code: Select all

1 2
Output:

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

shipu_a
New poster
Posts: 23
Joined: Tue Oct 23, 2012 8:04 pm
Location: Dhaka,Bangladesh
Contact:

371 - Ackermann Functions...Why TLE

Post by shipu_a »

TLE plz help..................... :( :oops:

Code: Select all

#include<iostream>
#include<algorithm>
#include<sstream>
#include<fstream>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#define ll long long
#define sc scanf
#define pf printf
#define pi 2*acos(0.0)
using namespace std;
int main()
{
    ll m,n,a,b,c,Max,Gn;
    while(sc("%lld%lld",&m,&n)==2)
    {
        Max=0;
        if(m==0&&n==0)
        break;
        a=min(m,n);
        b=max(m,n);
        for(ll i=a;i<=b;i++)
        {
            int p=i;
            c=0;
            if(p%2==0)
            {
                p/=2;
                c++;
            }
            else
            {
                p=3*p+1;
                c++;
            }
            while(p!=1)
            {
                if(p%2==0)
                {
                    p/=2;
                    c++;
                }
                else
                {
                    p=3*p+1;
                    c++;
                }

            }
            if(c>Max)
            {
                Max=c;
                Gn=i;
            }
        }

        pf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",a,b,Gn,Max);

    }
    return 0;
}
Nothing is imposible in the world.....And
Never Judge a Book by Its Cover.............
BUBT_Psycho
http://uhunt.felix-halim.net/id/168573
http://shipuahamed.blogspot.com

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 371 - Ackermann Functions...Why TLE

Post by lbv »

shipu_a wrote:TLE plz help..................... :( :oops:
Reading comprehension can be tricky sometimes, but it's a skill that requires plenty of attention when solving algorithm problems. For example, in this problem, think about the meaning of this sentence (from the problem statement):
The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long.
At first, you might think that using a 32-bit signed integer might work, but actually, the problem statement says nothing about a signed 32-bit integer, so it's a good idea not to assume that it should be signed. Hence, try for example changing the type of your p variable from "int" to "unsigned int".

Try for example this case:

Code: Select all

800000 900000
0 0

Code: Select all

Between 800000 and 900000, 837799 generates the longest sequence of 524 values.

sakibrahman
New poster
Posts: 3
Joined: Wed May 22, 2013 10:33 pm

uva 371 WA

Post by sakibrahman »

#include <stdio.h>
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
long long int sequence[10000000+5];
long long int seq2[10000000+5];
long long int ackerman(long long int a)
{
long long int sequence = 0;
if(a==1) sequence = 3;
else
{
while(a!=1)
{
if(a%2==0) a = a / 2;
else a = 3 * a +1;
sequence++;
}
}

return sequence;


}


int main()
{

long long int i,j,k,m,n,o,p,q,a,b;
while(scanf("%lld %lld",&a,&b)&&a!=0&&b!=0)
{
if(a>b) {m = a;a = b; b = m;}
for(i=a;i<=b;i++)
{
sequence = ackerman(i);
}



i=a;
for(k = 0; k<(b-a);k++)
{
seq2[k] = sequence;
i++;
}
sort(seq2,seq2+k);
long long int largest = seq2[k-1];


i = a;
while(i!=b+1)
{
// cout<<i<<": "<<sequence<<endl;
if(sequence==largest)
{
printf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",a, b, i, largest);
break;
}
i++;
}

}




}


I'm just blushed out and dissapointed! :(

Post Reply

Return to “Volume 3 (300-399)”