Page 1 of 1

10479 - The Hendrie Sequence

Posted: Wed Apr 16, 2003 12:27 pm
by erfan
Here input is 19 digit (maximum).In long double it can not handle.Can anyone tell me how it possible to take input and also handle?
I solve it but can possible for 18 digit input.

Posted: Wed Apr 16, 2003 2:17 pm
by bery olivier
Each test case consists of a single line containing the integer n ( 0 < n < (2^63))
This fits in long long. OJ can handle. As the numbers are positive, you can also use unsigned for more safe.

Posted: Thu Apr 17, 2003 1:56 pm
by erfan
Yah, i use long long but WA.May be in my code is wrong for some case.Can any one help me by some critical input output:

Posted: Sat Apr 19, 2003 7:11 am
by erfan
Thanks bery olivier, At last i got AC it with long long.

Posted: Sun Oct 05, 2003 8:59 pm
by Larry
Can someone post some input/output?

Posted: Mon Oct 06, 2003 6:43 am
by Per
Input:

Code: Select all

63
64
44
806856837013209088
80685
1424216473284256275
987655432
9223372036854775807
9223372036854775808
0
Output:

Code: Select all

0
6
3
16
0
1
4
0
63
Note that the last case is illegal, so if your program doesn't handle it correctly, it's no biggie.

Posted: Mon Oct 06, 2003 10:46 am
by Larry
ya, I actually got AC, thanks Per.

I think this problem was very nice. How does one go about solving it? I basically wrote a brute force program and looked over the first 200 numbers and guessed at a pattern - took me about an hour.. is there a more systematic way of doing it?

Posted: Mon Oct 06, 2003 7:13 pm
by Per
Yup, that's what I did as well (and I have a friend who solved it this way too), though I computed the first numbers by "hand" (or actually, by cut'n'paste).

Other ways... I don' know, maybe some lisp guru could do some funky lazy evaluation stuff. ;)
It doesn't seem very probable though, I think it's hard to devise a general method.

Posted: Tue Jul 20, 2004 1:34 pm
by Subeen
I got WA with this problem. Please help me to find my bug.
[cpp]#include <stdio.h>
#include <math.h>

int depth, ans;
long long int serial, current;

int recurse(int n, int d)
{
int i, tempDepth;
long long int tempCurrent;

if(d==depth)
{
if(serial==current+1)
{
ans = n;
return 1;
}
else
return 0;
}

for(i=0; i<n; i++)
{
tempDepth = depth - d - 1;
if(tempDepth > 0)
tempCurrent = current + (long long int) (pow(2, tempDepth-1));
else
tempCurrent = current + 1;
if(serial <= tempCurrent)
{
if(recurse(0, d+1))
return 1;
}
else
current = tempCurrent;
}
if(recurse(n+1, d+1))
return 1;
return 0;
}

int main()
{
long long int n;
double m;

while(1==scanf("%lli", &n) && n)
{
if(n==1)
{
printf("0\n");
continue;
}
m = ceil(log((double)n)/ log(2.0) - 0.000001);
depth = (int) m;
serial = n - (long long int)pow(2.0, m-1);
current = 0;
recurse(0, 0);
printf("%d\n", ans);
}

return 0;
}[/cpp]

Posted: Sat Jul 24, 2004 6:48 am
by erfan
Your code is seems to right for long input but some of
long long input(In VC __int64) it may be wrong i think.
As:
Input:9223372036854775808
Output:63
But your result is:0
So try with it in VC by using __int64.
Hope it will be help.

Posted: Mon Jul 26, 2004 5:03 pm
by Subeen
I think the input is not a valid one.

Code: Select all

Each test case consists of a single line containing the integer n ( 0 < n < 2^63) 

Posted: Fri Aug 06, 2004 4:37 am
by tep
I don't understand the problem...

The Hendrie Sequence ``H" is a self-describing sequence defined as follows:

H(1) = 0
If we expand every number x in H to a subsequence containing x 0's followed by the number x + 1, the resulting sequence is still H (without its first element).
Thus, the first few elements of H are:
0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,...

Can anyone explain why the sequence like tat?

regards,
stephanus

Posted: Sat Aug 14, 2004 5:55 pm
by Subeen
tep, see the tree below:

Code: Select all

                    0
                    |
                    1
                   /  \
                  0    2
                 /   / | \
                1   0  0  3
now start traversing each level left to right
hope it helps...

but I got WA with my code :( some one please post some test cases.

10479 - The Hendrie Sequence WA

Posted: Mon Feb 24, 2014 3:57 am
by hpjhc
Get AC

Re: 10479 - The Hendrie Sequence WA

Posted: Mon Feb 24, 2014 7:22 am
by uDebug
Have you even looked at this thread?

http://online-judge.uva.es/board/viewto ... 479#p10598

If you expect people to look at your code, the least you can do is make your code readable by using the code tags.