371  Ackermann Functions
Moderator: Board moderators
hint for 371
Only one hint need for this problem
if l>h then swap(l,h)
{code for find longest seq}
out (l,h,minnumberwhenseqlongest,seqlong)
ONLY ONE HINT. NOT MORE
the type wich need simple signed 32 bit (read carefuly problem:
"The largest value in the sequence will not be larger than can be accomodated in a 32bit Pascal LongInt or C long"
so not only l & h in longint but all!!! number in seg in longint(<2^311)
if l>h then swap(l,h)
{code for find longest seq}
out (l,h,minnumberwhenseqlongest,seqlong)
ONLY ONE HINT. NOT MORE
the type wich need simple signed 32 bit (read carefuly problem:
"The largest value in the sequence will not be larger than can be accomodated in a 32bit Pascal LongInt or C long"
so not only l & h in longint but all!!! number in seg in longint(<2^311)

 Experienced poster
 Posts: 131
 Joined: Sat Jul 17, 2004 4:09 am
 Location: Lima, Per
Hi QulinXao.
According to the statement
According to the statement
Therefore H>=L always , so isnL = the lower boundary value in the sequence
H = the upper boundary value in the sequence
Last edited by Antonio Ocampo on Thu Jan 06, 2005 9:36 pm, edited 1 time in total.
371 in 0.693 s
Hey! If anyone wants to know how to get 371 AC in .7 s feel free to bug me.
I used memoization.
I used memoization.
All
ravi,IITM.
ravi,IITM.
Please HELP! 371 WA
What's wrong in my code?
Code: Select all
#include <iostream.h>
void main()
{
long long i,j,n,max,v,c,t,tmp;
cin>>i>>j;
while(i!=0)
{
v=1;
max=0;
if(i>j) {tmp=j;j=i;i=tmp;}
for(t=i;t<=j;t++)
{
c=0;
n=t;
while(n!=1)
{
c++;
if(n%2==1) n=3*n+1;else n/=2;
}
if(c>maxv==1) {max=c;v=t;}
}
cout<<"Between "<<i<<" and "<<j<<", "<<v<<" generates the longest sequence of "<<max<<" values."<<endl;
cin>>i>>j;
}
}
Hi, neno_uci, Andrei,
If the sequence length for N=1 is 1 then what is the sequence
length for N=2 ? Should be 2, if we follow your logic.
On the contrary, if we follow the logic of their example the
sequence length for N=2 should be 1.
They have this example:
[10] 5 16 8 4 2 1 {6}
10 > 5 > 16 > 8 > 4 > 2 > 7
We have 7 numbers in this chain but the answer for N=10
is 6 ( according to this example they give ).
So for N=2 we have:
[2] 1 {1}
because
2 > 1
What do you think ?
I am personally a little bit confused.
I get WA for the moment and
I am trying to get at least TLE and then to try to
optimize my algorithm.
If the sequence length for N=1 is 1 then what is the sequence
length for N=2 ? Should be 2, if we follow your logic.
On the contrary, if we follow the logic of their example the
sequence length for N=2 should be 1.
They have this example:
[10] 5 16 8 4 2 1 {6}
10 > 5 > 16 > 8 > 4 > 2 > 7
We have 7 numbers in this chain but the answer for N=10
is 6 ( according to this example they give ).
So for N=2 we have:
[2] 1 {1}
because
2 > 1
What do you think ?
I am personally a little bit confused.
I get WA for the moment and
I am trying to get at least TLE and then to try to
optimize my algorithm.
Sample I/O for anyone who is attacking this quite tricky
( in my opinion ) problem.
INPUT
OUTPUT
( in my opinion ) problem.
INPUT
Code: Select all
2147483647 2147483647
1 20
35 55
1 1
20 1
1000001 1200000
1000000 1000000
2000000 2000000
4000000 4000000
2147483647 2147483647
1000003 5000005
16 16
1 2
58 58
19 19
1 3
1 2
2 2
0 0
OUTPUT
Code: Select all
Between 2147483647 and 2147483647, 2147483647 generates the longest sequence of 450 values.
Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.
Between 1 and 1, 1 generates the longest sequence of 3 values.
Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 1000001 and 1200000, 1117065 generates the longest sequence of 527 values.
Between 1000000 and 1000000, 1000000 generates the longest sequence of 152 values.
Between 2000000 and 2000000, 2000000 generates the longest sequence of 153 values.
Between 4000000 and 4000000, 4000000 generates the longest sequence of 154 values.
Between 2147483647 and 2147483647, 2147483647 generates the longest sequence of 450 values.
Between 1000003 and 5000005, 3732423 generates the longest sequence of 596 values.
Between 16 and 16, 16 generates the longest sequence of 4 values.
Between 1 and 2, 1 generates the longest sequence of 3 values.
Between 58 and 58, 58 generates the longest sequence of 19 values.
Between 19 and 19, 19 generates the longest sequence of 20 values.
Between 1 and 3, 3 generates the longest sequence of 7 values.
Between 1 and 2, 1 generates the longest sequence of 3 values.
Between 2 and 2, 2 generates the longest sequence of 1 values.
Last edited by Sedefcho on Sat Mar 12, 2005 6:33 pm, edited 1 time in total.
I have found what my problems were.
Quite quite unpleasant tricky stuff.
1) They have test cases where L > H. Anyway, no problem about
that, OK, we swap them. So now we have L < H. But when we print
our answer we have to print L and H in increasing order ( in the order
they are after they are swapped ). So in these cases we
actually do not print " Between L ... H ... "but we print
"Between H ... L ... ".
And I was previously printing them in the order in which they
appear in the INPUT. So for input
the correct output is :
and not :
That is the first thing I wanted to mention.
2) The answer ( the sequence length ) for 1 is THREE ( 3 ). So we
should really comply with
what they show in their samples. And it is NOT TRUE that the
answer ( the sequence length ) for 1 is ONE ( 1 ). So for instance
for the input
the correct output is:
That is the second thing that is worth mentioning in my opinion.
Quite quite unpleasant tricky stuff.
1) They have test cases where L > H. Anyway, no problem about
that, OK, we swap them. So now we have L < H. But when we print
our answer we have to print L and H in increasing order ( in the order
they are after they are swapped ). So in these cases we
actually do not print " Between L ... H ... "but we print
"Between H ... L ... ".
And I was previously printing them in the order in which they
appear in the INPUT. So for input
Code: Select all
20 1
Code: Select all
Between 1 and 20, 18 generates the longest sequence of 20 values.
Code: Select all
Between 20 and 1, 18 generates the longest sequence of 20 values.
2) The answer ( the sequence length ) for 1 is THREE ( 3 ). So we
should really comply with
what they show in their samples. And it is NOT TRUE that the
answer ( the sequence length ) for 1 is ONE ( 1 ). So for instance
for the input
Code: Select all
1 2
Code: Select all
Between 1 and 2, 1 generates the longest sequence of 3 values.
Most probably you enter in some endless loop
when you are using the stdio.h.
I mean the TLE does not occur
because stdio.h is slower.
The fact that your Input Handling ( using stdio.h ) works on
your machine does not mean it will work on the Judge machine.
I mean sometimes there are some minor compatibility/portability
issues which lead to problems similar to the one you describe.
when you are using the stdio.h.
I mean the TLE does not occur
because stdio.h is slower.
The fact that your Input Handling ( using stdio.h ) works on
your machine does not mean it will work on the Judge machine.
I mean sometimes there are some minor compatibility/portability
issues which lead to problems similar to the one you describe.
About 371
What Do You Mean By ENDLESS LOOP When Using <stdio.h> Sedefcho.
I Get Acc Using <stdio.h> And It Look's To Me Very Strange TO jaracz
That Ac When <iostream.h> But TLE When <stdio.h>
Can You Explaine Me More.
Thank's In Advance
Rocky
I Get Acc Using <stdio.h> And It Look's To Me Very Strange TO jaracz
That Ac When <iostream.h> But TLE When <stdio.h>
Can You Explaine Me More.
Thank's In Advance
Rocky