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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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

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 »

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 »

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

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

Post by mohiul alam prince »

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

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

long long

Post by sohel »

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.

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

Post by mohiul alam prince »

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.

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

Post by mohiul alam prince »

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)”