SPOJ.com - Problem FIBBIT

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

Submit solution!

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

Submit solution!

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