## 10479 - The Hendrie Sequence

Moderator: Board moderators

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:

### 10479 - The Hendrie Sequence

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.

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:
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.
Not AC yet AC at last

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
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:

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
Thanks bery olivier, At last i got AC it with long long.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post some input/output?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
[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]

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
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
So try with it in VC by using __int64.
Hope it will be help.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
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) ``
Last edited by Subeen on Sat Aug 14, 2004 5:40 pm, edited 1 time in total.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:
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

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
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.

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### 10479 - The Hendrie Sequence WA

Get AC
Last edited by hpjhc on Mon Feb 24, 2014 8:40 am, edited 5 times in total.

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10479 - The Hendrie Sequence WA

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.
Check input and AC output for over 7,500 problems on uDebug!