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

Aengus
New poster
Posts: 12
Joined: Thu Oct 30, 2003 1:38 pm
Location: St. Petersburg, Russia
Contact:

Post by Aengus » Thu Oct 30, 2003 5:10 pm

It's funny, that everything is exactly the same that I've thought. May be somebody can check the code:
[c]#include <stdio.h>

unsigned next(unsigned a) {
if (a == 1) return 0;

if (a % 2 == 0) return a / 2;
else return 3*a + 1;
}

int seq_len(unsigned a) {
int steps = 0;

if (a == 1) return 3;

while (a = next(a)) steps++;

return steps;
}

int main(void) {
unsigned l, h, t, i, max, v, len;

while (1) {
scanf("%u %u", &l, &h);
if (l == 0) break;

printf("Between %lu and %lu, ", l, h);

if (l > h) {
t = l; l = h; h = t;
}

max = 0; v = 0;
for (i = l; i <= h; i++) {
len = seq_len(i);
if (len > max) {
max = len;
v = i;
}
}

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

return 0;
}[/c]
[/c]

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

check this input & output

Post by osan » Sat Nov 08, 2003 8:19 pm

Dear Aengus

Check these
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.
this time WA
what next...............?

Aengus
New poster
Posts: 12
Joined: Thu Oct 30, 2003 1:38 pm
Location: St. Petersburg, Russia
Contact:

Re: check this input & output

Post by Aengus » Sat Nov 08, 2003 11:04 pm

Osan,

Thank you for your answer, but I tried not to swap values if first is greater than the second and nothing changed. Besides, it is not clear from the statement of the problem, what to output in case of L>H. The sequence starting with 1 has length 3 (it is the example in the problem), the sequence starting with 2 has length 2, so it should be right.

I want to add, that I've spent quite a lot of time on that problem. First I tried the code that I showed in my last message. Than I added a check that the next value will not be greater than 2^32-1 similar to one in the problem 694 (which I succesfuly solved). I've got runtime error that ment that the sequence members may grow beyond the limit of unsigned long. Then I've used several functions for long arithmetic (which I also succesfuly used in several other problems). Now I could get the answer for any interval within 1 .. 2^32-1. But I once again got WA for that solution. I can't figure out any problems with any of my solutions.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

Post by osan » Sun Nov 09, 2003 1:08 pm

Aengus,

I think you didn
this time WA
what next...............?

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

Post by osan » Sun Nov 09, 2003 1:09 pm

onece again telling you remove your code from the forum.
Last edited by osan on Sun Nov 09, 2003 1:27 pm, edited 1 time in total.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

Post by osan » Sun Nov 09, 2003 1:12 pm

Aengus,

I think you didn
this time WA
what next...............?

Aengus
New poster
Posts: 12
Joined: Thu Oct 30, 2003 1:38 pm
Location: St. Petersburg, Russia
Contact:

AC at llast

Post by Aengus » Sun Nov 09, 2003 1:33 pm

Oh, thank you! The trouble was really in that point.

seadoo
New poster
Posts: 12
Joined: Mon Dec 15, 2003 6:16 pm

371: why SIGSEGV

Post by seadoo » Mon Dec 15, 2003 6:21 pm

Hello all!

Why am I getting SIGSEV error with this piece of code?
The largest value in the sequence will not be larger than a 32-bit C long, and I have long's in the code. What else could be wrong?
Last edited by seadoo on Mon Dec 15, 2003 6:31 pm, edited 1 time in total.

seadoo
New poster
Posts: 12
Joined: Mon Dec 15, 2003 6:16 pm

Post by seadoo » Mon Dec 15, 2003 6:31 pm

Got it... changed to unsigned long and it worked...

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

371 TLE why

Post by mohiul alam prince » Wed Feb 25, 2004 7:47 am

this is my code why i am getting TLE
BUT i have solved 100 & 694
[cpp]
#include <stdio.h>
#include <math.h>

double cycle(long m)
{
double i = 0;

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


int main()
{
long m,n,x,x1;
long mOriginal,nOriginal;
double temp,max,max1,min;
long i;

while (scanf("%ld %ld",&m,&n)==2){

if(n==0&&m==0)break;
mOriginal = m;
nOriginal = n;

if (m > n){
temp = m;
m = n;
n = temp;
}

max = cycle(m);
x=m;
for(i=m+1;i<=n;i++) {
temp = cycle(i);
if (temp > max){
max = temp;
x=m;
}
}
printf("Between %ld and %ld, %ld generates the longest sequence of %.0lf values.\n",mOriginal,nOriginal,x,max);

}
return 0;
}[/cpp][/cpp][/c]

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

about 371

Post by osan » Fri Mar 05, 2004 6:45 pm

long's range 2^31-1
in the problem they told about 32 bit number.
how can u hold the number in long???
u can use unsigned long
or double
this time WA
what next...............?

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Mar 10, 2004 3:00 pm

i have used double don't u see it?
any thing ????????

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

long long

Post by sohel » Wed Mar 10, 2004 3:16 pm

Why use double when you can use long long.
I used long long and got AC.

you have used double in the wrong place.
The cycle length will not be that huge but
the value 3n + 1 might be.

Make the appropriate modification and get AC.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Mar 10, 2004 3:20 pm

the range of long long & double are equal
and i have used long long for all variables but still TLE
Last edited by mohiul alam prince on Wed Mar 10, 2004 3:23 pm, edited 1 time in total.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Mar 10, 2004 3:22 pm

sohel
whats ur algo can u explain
i have solve 694 & 100
but i am getting TLE

Post Reply

Return to “Volume 3 (300-399)”