10479 - The Hendrie Sequence

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

10479 - The Hendrie Sequence

Post by erfan » Wed Apr 16, 2003 12:27 pm

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:

Post by bery olivier » Wed Apr 16, 2003 2:17 pm

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 Image AC at last Image

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

Post by erfan » Thu Apr 17, 2003 1:56 pm

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
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Sat Apr 19, 2003 7:11 am

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:

Post by Larry » Sun Oct 05, 2003 8:59 pm

Can someone post some input/output?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Oct 06, 2003 6:43 am

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:

Post by Larry » Mon Oct 06, 2003 10:46 am

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

Post by Per » Mon Oct 06, 2003 7:13 pm

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
Location: Bangladesh
Contact:

Post by Subeen » Tue Jul 20, 2004 1:34 pm

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

Post by erfan » Sat Jul 24, 2004 6:48 am

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

Post by Subeen » Mon Jul 26, 2004 5:03 pm

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:

Post by tep » Fri Aug 06, 2004 4:37 am

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
Location: Bangladesh
Contact:

Post by Subeen » Sat Aug 14, 2004 5:55 pm

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

Post by hpjhc » Mon Feb 24, 2014 3:57 am

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

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

Re: 10479 - The Hendrie Sequence WA

Post by uDebug » Mon Feb 24, 2014 7:22 am

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!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 104 (10400-10499)”