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

Post Reply
User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue May 03, 2005 10:34 am

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.

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

About 371

Post by Rocky » Thu May 05, 2005 11:14 am

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Thu May 05, 2005 1:25 pm

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
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

Why WA??

Post by KvaLe » Thu May 05, 2005 4:44 pm

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);
} 
Giorgi Lekveishvili

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

ON Discuss About 371

Post by Rocky » Mon May 09, 2005 7:48 am

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
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

371 why WA

Post by thinker_bd » Thu Jul 21, 2005 9:06 pm

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
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

371 why WA

Post by thinker_bd » Thu Jul 21, 2005 9:08 pm

thanx mr. raj i just make max=0 after every print and got accpted
code removed
Last edited by thinker_bd on Sat Jul 23, 2005 9:09 pm, edited 1 time in total.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Post by Raj Ariyan » Sat Jul 23, 2005 7:47 am

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 .
Some Love Stories Live Forever ....

shu
New poster
Posts: 6
Joined: Sat Jul 16, 2005 1:43 pm
Contact:

Post by shu » Sun Aug 14, 2005 12:23 pm

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

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Aug 14, 2005 8:28 pm

shu wrote: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 :wink:
shu wrote:unsigned int is not enough :P
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 :P

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Post by marcadian » Tue Aug 23, 2005 4:41 pm

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
New poster
Posts: 1
Joined: Sat Aug 27, 2005 7:07 pm

WHY WRONG???371

Post by Mirfat Akter Sharmin » Sat Aug 27, 2005 7:14 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

hmm..

Post by helloneo » Sun Aug 28, 2005 7:28 am

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
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Location: SUST, BANGLADESH
Contact:

ABOUT 371

Post by roni » Sat Sep 10, 2005 3:01 am

output the boundaries in sorted order.
roni(SUST)

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

about data type

Post by Rocky » Tue Sep 13, 2005 3:36 pm

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

Post Reply

Return to “Volume 3 (300-399)”