EllysCode01
TCO17 Warsaw · 2017-03-31 · by espr1t
TCO17 Warsaw · 2017-03-31 · by espr1t · Encryption/Compression, Simple Math
Problem Statement
Problem Statement
Elly came up with an infinite sequence of zeroes and ones.
The sequence can be incrementally constructed as follows:
Begin by writing down a zero. Then, repeat the following process forever:
The positions in the sequence are numbered sequentially, starting from zero.
To impress Elly you want to write a program which can quickly answer any question of the following type: "How many ones are in Elly's sequence at positions from L to R, inclusive?"
You are given thelong s L and R.
Return the total number of ones whose positions lie in the interval [L, R].
Begin by writing down a zero. Then, repeat the following process forever:
- Copy the entire sequence, but change each zero into a one and vice versa.
- Append the copy to the current sequence.
The positions in the sequence are numbered sequentially, starting from zero.
To impress Elly you want to write a program which can quickly answer any question of the following type: "How many ones are in Elly's sequence at positions from L to R, inclusive?"
You are given the
Constraints
- L and R will be between 0 and 10^18, inclusive.
- L will be less than or equal to R.
Examples
0)
5 15 Returns: 5
The interval [5, 15] covers the digits 01101[00110010110]1001011001101001. This subsequence contains 5 ones, so the correct answer is 5.
1)
101 185 Returns: 42
The answer is 42.
2)
0 0 Returns: 0
The digit at index zero is 0.
3)
1 1 Returns: 1
The digit at index one is 1.
4)
1337 1337 Returns: 0
The digit at 1337-th position is 0.
Submissions are judged against all 156 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysCode01 with a public method long long getOnes(long long L, long long R) · 156 test cases · 2 s / 256 MB per case