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:

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:

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.