FIBBIT - FIBO BIT

no tags 

Count the number of numbers between two 64 bit numbers A, B that have the sum of their bits equal to a Fibonacci number. For example, between 15 and 17 there are two numbers that have sum of bits equal to a Fibonacci number.

15: 1111 sum=4
16: 10000 sum=1 (Fibonacci)
17: 10001 sum=2 (Fibonacci).

Input

The 2 numbers A and B.

A < B < 10^18.

Output

The number of such numbers between both A and B inclusive.

Example

Input:
15 17

Output:
2

hide comments
Mitch Schwartz: 2012-08-03 14:36:51

Why have you changed the limit from 10^18 to 2^18? I think this is a wrong decision. Please change it back to 10^18 and consider the changes I recommended, or else please move this to tutorial.

Note: I recommend at least 1000 test cases for some input file, probably 5000 is better.

Another note: This is essentially an easier version of GONE (and some other related problems), that's why I made these suggestions, otherwise I think it's really not interesting for classical.

Last edit: 2012-08-03 08:16:40
Mitch Schwartz: 2012-08-03 14:36:51

This is similar to some other problems in classical, but I think it may be different enough that people won't mind keeping it here.

May I request putting multiple test cases in an input file? It is possible to handle quite a few test cases in 0.00 with a straightforward approach and no optimisation.

My second submission should be able to handle the problem as written as well as an integer T on a line followed by T lines each with its own test case... only, it got WA... it operated by looking for a space character to test the situation, so I think at least one of your input files isn't well formatted for the problem as written (i.e., does not contain two space-separated integers).

Jared Deckard: 2012-08-03 14:36:51

start < end < 10^18 ?
2^64 ~ 10^19.2659


Added by:priyamehtanit
Date:2012-08-02
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64