371 - Ackermann Functions

[Sedefcho]

Well, the point is not that jaracz is using stdio.h or iostream.h.
The point is that ( if I am right, of course ) in the first case
( when uses stdio.h and when he gets TLE ) he does not handle the
input correctly so his program enters some endless
loop WHILE in the second case ( when he uses iostream.h )
he obviously handles the input correctly so his program terminates.

And as his algorithm is apparently right in the first
case he gets TLE and in the second case he gets ACC. That's it.

I mean if he uses one and the same algorithm in his two programs
and the only difference between these two programs is the input
handling ( stdio.h vs iostream.h ) the only reason for the TLE could
only be that he does not handle the input in the correct way.

Of course I can not be 100% sure about that but that is the only
logical explanation if I understand him correctly.

[Rocky]

Hi Sedefcho Rocky Again,
Thank You Very Much.Now I Understand That The Matter Of TLE For Using <iostream> & <stdio>.
But One Thing You Say That The TLE Is Happen For Maneging The INPUT.
Can It Happen For OUTPUT.That is , Is IT Can't Happen That jaracz Manage The Input But Not The Output.Also IT Can Be Happen That He Can't Manage The BOTH INPUT & OUTPUT.But In The Case of OUTPUT Or INPUT The Case Occure Frist & He Get's TLE.
Am I Right.I Thing It Is Easy To Discuss In That Fact If We Can See The jaracz's Code.
By The Way Thank You Very Much.

Rocky

[Sedefcho]

Well, Rocky

Of course, theoretically jaracz could have a problem
with his output handling too.

If he has a piece of code like

Code: Select all

while (1) { 
   cout << "1\n";
}

that would also result in a TLE

[KvaLe]

Hi.
Here is my code, it gets WA.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main (void) {
  long long I, K, N, L, H, S, V, TMP;
  while (scanf ("%d%d", &L, &H) != EOF) {
    if (! L && ! H) break;
    if (L > H) TMP = L, L = H, H = TMP;
    for (I = L; I <= H; I++) {
      N = I, K = 0;
      do {
        if (N%2 == 0) N /= 2;
        else N = 3*N+1;
        K++;
      } while (N != 1);
      if (K > S) S = K, V = I;
    } 
    printf ("Between %d and %d, %d generates the longest sequence of %d values.\n", L, H, V, S);
  } 
  exit (0);
} 

[Rocky]

To Sedefcho
Yeahh... You Are Right Sedefcho.

TO KvaLe.
I Do Not Debug Or Test Your Code But I Think There Some Problem In Take The Input,That
Is For long long It Will be scanf("%lld",&...) & you use scanf("%ld",&...).
Try With This.

GOOD LUCK
ROCKY

[thinker_bd]

whats wrong here i got WA

#include<stdio.h>

unsigned long fun(unsigned long i)
{
unsigned long count=0;
while(i!=1||(count==0))
{
if(((i%2)==0))
i=i/2;
else
i=(3*i)+1;
count++;
}
return count;
}


int main()
{
unsigned long a, b,tmp,i,value;
unsigned long print_a,print_b;
unsigned long new_max=0,max=0;

//freopen("371.txt","r",stdin);

while(scanf("%ld %ld",&a,&b))
{
if(a==0&&b==0)
break;
print_a=a;
print_b=b;

if(a>b)
{
tmp=a;
a=b;
b=tmp;
}
value=a;

for(i=a;i<b;i++)
{
new_max=fun(i);
if(new_max>max)
{
max=new_max;
value=i;
}
}
printf("Between %u and %u, %u generates the longest sequence of %u values.\n",print_a,print_b,value,max);
}
return 0;
}

[thinker_bd]

thanx mr. raj i just make max=0 after every print and got accpted
code removed

[Raj Ariyan]

Hi thinker,
Try this input and outputs. Good luck.

Input :-

Code: Select all

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

Your output :-

Code: Select all

Between 42 and 18, 27 generates the longest sequence of 111 values.
Between 35 and 1, 1 generates the longest sequence of 111 values.
Between 20 and 25, 20 generates the longest sequence of 111 values.
Between 29 and 9, 9 generates the longest sequence of 111 values.
Between 13 and 15, 13 generates the longest sequence of 111 values.
Between 6 and 46, 6 generates the longest sequence of 111 values.
Between 32 and 28, 28 generates the longest sequence of 111 values.
Between 12 and 42, 12 generates the longest sequence of 111 values.
Between 46 and 43, 43 generates the longest sequence of 111 values.
Between 28 and 37, 28 generates the longest sequence of 111 values.
Between 42 and 5, 5 generates the longest sequence of 111 values.
Between 3 and 4, 3 generates the longest sequence of 111 values.
Between 43 and 33, 33 generates the longest sequence of 111 values.
Between 22 and 17, 17 generates the longest sequence of 111 values.
Between 19 and 46, 19 generates the longest sequence of 111 values.
Between 48 and 27, 27 generates the longest sequence of 111 values.
Between 22 and 39, 22 generates the longest sequence of 111 values.
Between 20 and 13, 13 generates the longest sequence of 111 values.
Between 18 and 50, 18 generates the longest sequence of 111 values.
Between 36 and 45, 36 generates the longest sequence of 111 values.

My Accepted program gives :-

Code: Select all

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.

I think u get it .

[shu]

[quote="Antonio Ocampo"]
Therefore H>=L always , so isn

[Antonio Ocampo]

I don't think so. I got WA if i don't swap when L > H. I think there're some test-cases where L > H.

I disagree because I got AC without considering that situation

unsigned int is not enough
2147483647 * 3 + 1 = 6442450942 (surely it exceed 4294967296)
use long long instead.

According to the statement: "The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long. " Therefore N=2^31-1 isn't a valid input.

Greetings

[marcadian]

ow I used longint in pascal and it's correct. but it must swap if l>u, because if i don't swap it, it got WA. why they say that
L = the lower boundary value in the sequence

H = the upper boundary value in the sequence
but they have test case where l>u

[Mirfat Akter Sharmin]

Why this is getting wrong answer??It is giving output correctly..Plz help...

Code: Select all

#include<stdio.h>

int maxlength(long int n){
	int len = 0;
	while(n>1){
		if(n%2==0){
			n/=2;
			len++;
		}
		else{
			n = 3*n +1;
			len++;
		}
	}
	return len;
}
void main(){
	long int i,k,in1,in2,temp;
	int max ,length;
	while(scanf("%ld %ld",&in1,&in2)==2){
	if(in1 == 0 && in2 == 0)
			break;
		max = 0;
		length = 0;
		if(in1>in2){
			temp =in1;
			in1 = in2;
			in2 = temp;
		}
		i = in1;
		for(;in1<=in2;in1++){
			if(in1 == 1){
				length = 0;
			}
			else{
				length = maxlength(in1);
			}
			if(length>max){
				max = length;
				k = in1;
			}
		}
		printf("Between %ld and %ld, %ld generates the longest sequence of %d values.\n",i,in2,k,max);
	}
}[/quote]

[helloneo]

for(;in1<=in2;in1++){
if(in1 == 1){
length = 0;
}
else{
length = maxlength(in1);
}

when in1 is 1 why the length is 0..?

[1] 4 -> 2 -> 1

[roni]

output the boundaries in sorted order.

[Rocky]

I think long long is need... for this problem