SparseOnes
SRM 832 · 2022-06-24 · by misof
Problem Statement
Consider all non-negative integers written in binary.
In this problem we'll call a non-negative integer good if its binary representation doesn't contain two consecutive ones. For example, 0, 2, 5, 10, 16 and 41 are good (in binary they are 0, 10, 101, 10000, 101001) while 3, 6, 11 are bad (in binary: 11, 110, 1011).
Let's take all good non-negative integers in order and let's concatenate their binary representations to get an infinite binary string S. The first few of these representations are 0, 1, 10, 100, 101, 1000, 1001, 1010 and thus the string begins S = 0110100101100010011010...
You are given the
Notes
- The substring S[x:y] contains of characters whose 0-based indices lie in the half-open interval [x,y).
Constraints
- 0 <= A < B <= 10^14.
0 22 Returns: 10
S[0:22] is the prefix shown in the problem statement: "0110100101100010011010". It contains 10 ones (and 12 zeros).
1 22 Returns: 10
S[1:22] is "110100101100010011010" (the same as previous example, except for the initial zero). It still contains 10 ones.
5 21 Returns: 7
S[5:21] is "0010110001001101".
0 100000000000000 Returns: 28502454998808
0 1 Returns: 0
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SparseOnes with a public method long long count(long long A, long long B) · 68 test cases · 2 s / 256 MB per case