Page 6 of 14
Posted: Mon Dec 20, 2004 11:31 am
by Rocky
YAAAA.. , GOOD ANSWER MATHICS
Take a Large Data Type That The Result Value During Runtime,That is (3*n+1,When n is a odd number of more than 8 digit) Can Store in it.
Thanks
GOOD LUCK
hint for 371
Posted: Mon Jan 03, 2005 12:33 pm
by QulinXao
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 32-bit Pascal LongInt or C long"
so not only l & h in longint but all!!! number in seg in longint(<2^31-1)
Posted: Thu Jan 06, 2005 5:04 am
by Antonio Ocampo
Hi QulinXao.
According to the statement
L = the lower boundary value in the sequence
H = the upper boundary value in the sequence
Therefore H>=L always , so isn
Posted: Thu Jan 06, 2005 4:43 pm
by CodeMaker
easy.......isn't it?
371 in 0.693 s
Posted: Tue Mar 08, 2005 6:25 pm
by sunmoon
Hey! If anyone wants to know how to get 371 AC in .7 s feel free to bug me.
I used memoization.
Please HELP! 371 WA
Posted: Thu Mar 10, 2005 9:33 pm
by Andrey
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>max||v==-1) {max=c;v=t;}
}
cout<<"Between "<<i<<" and "<<j<<", "<<v<<" generates the longest sequence of "<<max<<" values."<<endl;
cin>>i>>j;
}
}
Posted: Fri Mar 11, 2005 12:46 am
by neno_uci
Hi Andrey, the length of the sequence generated by 1 is 1, there is your mistake, replace your
while (n != 1) { ... } loop by
do { ... } while (n != 1);
and the work is done...
best wishes,
Yandry.
Posted: Sat Mar 12, 2005 5:50 pm
by Sedefcho
The values for L and H can not be negative, right ? Or do we
have to consider negative values too ?
( Don't bother to answer now ! There're no
negative values for L and H in the input )
Posted: Sat Mar 12, 2005 6:03 pm
by Sedefcho
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.
Posted: Sat Mar 12, 2005 6:11 pm
by Sedefcho
Sample I/O for anyone who is attacking this quite tricky
( 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.
Posted: Sat Mar 12, 2005 6:24 pm
by Sedefcho
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 :
Code: Select all
Between 1 and 20, 18 generates the longest sequence of 20 values.
and not :
Code: Select all
Between 20 and 1, 18 generates the longest sequence of 20 values.
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:
Code: Select all
Between 1 and 2, 1 generates the longest sequence of 3 values.
That is the second thing that is worth mentioning in my opinion.
Posted: Sun Mar 13, 2005 7:35 pm
by Andrey
Thank u very much, i got AC!
Posted: Mon May 02, 2005 1:44 am
by jaracz
I wonder 'cause i got TLE using <stdio.h> library but AC using <iostream> algo in both was the same, this's strange isn't it?:|
Posted: Mon May 02, 2005 1:24 pm
by Sedefcho
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.
About 371
Posted: Tue May 03, 2005 7:45 am
by Rocky
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