| Submit | All submissions | Best solutions | Back to list |
FIBBIT - FIBO BIT |
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
| 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 |
hide comments
|
2012-08-03 14:36:51 Mitch Schwartz
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 |
|
|
2012-08-03 14:36:51 Mitch Schwartz
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). |
|
|
2012-08-03 14:36:51 Jared Deckard
start < end < 10^18 ? 2^64 ~ 10^19.2659 |
RSS