10479 - The Hendrie Sequence

[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.

[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.

[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:

[erfan]

Thanks bery olivier, At last i got AC it with long long.

[Larry]

Can someone post some input/output?

[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.

[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?

[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.

[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]

[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.

[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) 

[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

[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.

[hpjhc]

Get AC

[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.